{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QAOA 求解最大割问题\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概览\n",
    "\n",
    "在[量子近似优化算法教程](./QAOA_CN.ipynb)中，我们介绍了如何将经典的组合优化问题编码为量子优化问题，并用量子近似优化算法 [1]（quantum approximate optimization algorithm, QAOA）求解。在本教程中，我们将以最大割问题为例来进一步阐述 QAOA。\n",
    "\n",
    "### 最大割问题\n",
    "\n",
    "最大割问题（Max-Cut Problem）是图论中常见的一个组合优化问题，在统计物理学和电路设计中都有重要应用。最大割问题是一个 NP 困难问题，因此目前并不存在一个高效的算法能完美地解决该问题。\n",
    "\n",
    "在图论中，一个图是由一对集合 $G=(V, E)$ 表示，其中集合 $V$ 中的元素为该图的顶点，集合 $E$ 中的每个元素是一对顶点，表示连接这两个顶点的一条边。例如下方图片中的图可以由 $V=\\{0,1,2,3\\}$ 和 $E=\\{(0,1),(1,2),(2,3),(3,0)\\}$ 表示。\n",
    "\n",
    "![G](figures/maxcut-fig-maxcut_g.png \"图 1：一个有四个顶点和四条边的图\")\n",
    "<div style=\"text-align:center\">图 1：一个有四个顶点和四条边的图 </div>\n",
    "\n",
    "\n",
    "一个图上的割（cut）是指将该图的顶点集 $V$ 分割成两个互不相交的集合的一种划分，每个割都对应一个边的集合，这些边的两个顶点被划分在不同的集合中。于是我们可以将这个割的大小定义为这个边的集合的大小，即被割开的边的条数。最大割问题就是要找到一个割使得被割开的边的条数最多。图 2 展示了图 1 中图的一个最大割，该最大割的大小为 $4$，即割开了图中所有的边。\n",
    "\n",
    "![Max cut on G](figures/maxcut-fig-maxcut_cut.png \"图 2：图 1 中图的一个最大割\")\n",
    "<div style=\"text-align:center\">图 2：图 1 中图的一个最大割 </div>\n",
    "\n",
    "\n",
    "假设输入的图 $G=(V, E)$ 有 $n=|V|$ 个顶点和 $m=|E|$ 条边，那么我们可以将最大割问题描述为 $n$ 个比特和 $m$ 个子句的组合优化问题。每个比特对应图 $G$ 中的一个顶点 $v$，其取值 $z_v$ 为 $0$ 或 $1$，分别对应该顶点属于集合 $S_{0}$ 或 $S_{1}$，因此这 $n$ 个比特的每种取值 $z$ 都对应一个割。每个子句则对应图 $G$ 中的一条边 $(u,v)$，一个子句要求其对应的边连接的两个顶点的取值不同，即 $z_u\\neq z_v$，表示该条边被割开。也就是说，当该条边连接这的两个顶点被割划分到不同的集合上时，我们说该子句被满足。因此，对于图 $G$ 中的每条边 $(u,v)$，我们有\n",
    "\n",
    "$$\n",
    "C_{(u,v)}(z) = z_u+z_v-2z_uz_v,\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "其中 $C_{(u,v)}(z) = 1$ 当且仅当该条边被割开。否则，该函数等于 $0$。整个组合优化问题的目标函数是\n",
    "\n",
    "$$\n",
    "C(z) = \\sum_{(u,v)\\in E}C_{(u,v)}(z) = \\sum_{(u,v)\\in E}z_u+z_v-2z_uz_v.\n",
    "\\tag{2}\n",
    "$$\n",
    "\n",
    "因此，解决最大割问题就是要找到一个取值 $z$ 使得公式（2）中的目标函数最大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 编码最大割问题\n",
    "\n",
    "为了将最大割问题转化为一个量子问题，我们要用到 $n$ 个量子比特，每个量子比特对应图 $G$ 中的一个顶点。一个量子比特处于量子态 $|0\\rangle$ 或 $|1\\rangle$，表示其对应的顶点属于集合 $S_{0}$ 或 $S_{1}$。值得注意的是，$|0\\rangle$ 和 $|1\\rangle$ 是 Pauli $Z$ 门的两个本征态，并且它们的本征值分别为 $1$ 和 $-1$，即\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Z|0\\rangle&=|0\\rangle,\\tag{3}\\\\\n",
    "Z|1\\rangle&=-|1\\rangle.\\tag{4}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "因此我们可以使用 Pauli $Z$ 门来构建该最大割问题的哈密顿量 $H_C$。因为通过映射 $f(x):x\\to(x+1)/2$ 可以将 $-1$ 映射到 $0$ 上 并且仍将 $1$ 映射到 $1$ 上，所以我们可以将式（2）中的 $z$ 替换为 $(Z+I)/2$（$I$ 是单位矩阵），得到原问题目标函数对应的哈密顿量\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "H_C &= \\sum_{(u,v)\\in E} \\frac{Z_u+I}{2} + \\frac{Z_v+I}{2} - 2\\cdot\\frac{Z_u+I}{2}\\frac{Z_v+I}{2}\\tag{5}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{Z_u+Z_v+2I - (Z_uZ_v+Z_u+Z_v+I)}{2}\\tag{6}\\\\\n",
    "&= \\sum_{(u,v)\\in E} \\frac{I - Z_uZ_v}{2}.\\tag{7}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "该哈密顿量关于一个量子态 $|\\psi\\rangle$ 的期望值为\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\langle\\psi|H_C|\\psi\\rangle &= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I - Z_uZ_v}{2}|\\psi\\rangle\\tag{8}\\\\\n",
    "&= \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{I}{2}|\\psi\\rangle - \\langle\\psi|\\sum_{(u,v)\\in E} \\frac{Z_uZ_v}{2}|\\psi\\rangle\\tag{9}\\\\\n",
    "&= \\frac{|E|}{2} - \\frac{1}{2}\\langle\\psi|\\sum_{(u,v)\\in E} Z_uZ_v|\\psi\\rangle.\\tag{10}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "如果我们记\n",
    "\n",
    "$$\n",
    "H_D = -\\sum_{(u,v)\\in E} Z_uZ_v,\n",
    "\\tag{11}\n",
    "$$\n",
    "\n",
    "那么找到量子态 $|\\psi\\rangle$ 使得 $\\langle\\psi|H_C|\\psi\\rangle$ 最大等价于找到量子态 $|\\psi\\rangle$ 使得 $\\langle\\psi|H_D|\\psi\\rangle$ 最大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Paddle Quantum 实现\n",
    "\n",
    "接下来，我们用量桨实现 QAOA 来求解最大割问题。有许多方法可以找到参数 $\\vec{\\gamma},\\vec{\\beta}$，我们这里使用经典机器学习中的梯度下降方法。\n",
    "\n",
    "要在量桨上实现 QAOA，首先要做的便是加载需要用到的包。其中 `networkx` 包可以帮助我们方便地处理图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:04.006915Z",
     "start_time": "2021-04-30T09:11:03.951557Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>pre { white-space: pre !important; }</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "display(HTML(\"<style>pre { white-space: pre !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.078417Z",
     "start_time": "2021-04-30T09:11:04.569758Z"
    }
   },
   "outputs": [],
   "source": [
    "# 加载量桨、飞桨的相关模块\n",
    "import paddle\n",
    "from paddle_quantum.circuit import UAnsatz\n",
    "from paddle_quantum.utils import pauli_str_to_matrix\n",
    "\n",
    "# 加载额外需要用到的包\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来，我们生成该最大割问题中的图 $G$。为了运算方便，这里的顶点从 $0$ 开始计数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.411878Z",
     "start_time": "2021-04-30T09:11:08.093215Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAj/0lEQVR4nO3deXyV1bXw8d8KgUAYo6KCcJuKgOKEc6vgRJVqnG61Uq1tUXCotCqKpbF2sINR63D1qnXAwnvb19q+ttdeG1vHq4JVq4iigqDgURFBZAqQBBKy3j/WDqAMkpznPM9zzlnfz4fPRzbJ8yxzstfZZz97ry2qinPOuXiUJB2Ac84VE0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXI0+6zjkXo9KkA3Bue1VW15YAA4BBQBegE7AOaADmAvMyNVUtyUXo3OcTL+3o0iok2RFAFTAc2AtoAZoBCX80/CnFPrnNBqYCtcCTnoRd2njSdalTWV1bAZwLTAC6A12xBLu9FFgD1AE3AZMzNVXLo47TufbwpOtSo7K6thy4HhiLjWjLI7hsPTYCngRMzNRU1UdwTefazZOuS4XK6trhwANABTZfG7UGYDkwKlNTNS0H13duu3jSdYmqrK4tA24BRpObZPtZDcAUYHympmptDPdz7lM86brEVFbXdgMeA4YST8Jt1QDMAEZmaqpWx3hf5zzpumSEhDsNGAx0TiCERmAOMMwTr4uTb45wsQtTCo+RXMIl3Hcw8GiIx7lYeNJ1SbgFm1JIKuG26gwcANyccByuiPj0gotVWKXwKPHO4X6eBuB4X9Xg4uBJ18UmrMN9G+ibdCxbsBAY6Ot4Xa759IKL0w3YOtw0qgCuSzoIV/h8pOtiEbb2LiT5edxtaQT6+pZhl0s+0nVxORfb2ptmLdgmDedyxke6LudCtbAFQJ+kY9kOC4H+Xp3M5YrX03VxGIFVC2u3YXvsxDGDe7NP354M6duD7p07bvi3b9zzPC+8uyzbGFv1AI4Fnojqgs5typOui0MVVp6x3b79pS9w/N67RhTONpUDJ+JJ1+WIJ10Xh+G0rR7uZhRYtLKRNxauZPXaZk4buls0kW2uBDgyVxd3zud0XU6F+dw1ZLlqoXPHEhqbbJr1S1/cgQcu+PKGf4t4egFss0TXTE2Vdw4XOV+94HJtALA+24u0JtyYtGBxOxc5T7ou1wZhZ5rlk2Ysbuci50nX5VoXspzPTYCQrtoQroB40nW51on8TLpe7tHlhCddl2vrsMUH+UQBP8rH5YQnXZdrDeRn0m1IOghXmDzpulybS/6tBy/F4nYucvnWGVz+mUcEb+4n7duH/fr1AqBvr08v+T3nS1/g2D13AWDmghX87fWPsr1dCRa3c5HzzREu5yqra6cDB2ZzjRvP2I8zDur/uV/34PQPmPDgzGxuBTA9U1N1cLYXcW5LfHrBxWEq+TOv2wI8m3QQrnD59IKLQy0wBujW3gtMeHBmFCPY7VEPPBLHjVxx8pGui8OTwKqkg9hOdcBTSQfhCpcnXZdzoSD4jdgoMs3qgRu9gLnLJU+6Li6TSf/vWwkwJekgXGFLeydwBeK9605asXbhnGktTenc6KWqDcC9fiilyzVPui7nROQLwN8X33/VV1oaVycdzha11K/ouPDe7/4p6Thc4fOk63JGREpEZBzwBjBSm9cuX/XSQ78Mo8rUaGlap0v+cm1p09IPnhGRG0WkPOmYXOHypOtyQkQGA88At2NLxR4E9lr54l9+LCJTSE9tgwYRuXfth7N/Hf5+BTBTRI5OLiRXyDzpukiJSEcR+SHwGjAMWAScrqpfV9XF4cvGAzOAxoTCbNUIzJDSjpeo6g+Aw4DXsVMj/ldE7haRnolG6AqObwN2kRGRA4D7gANC02TgClXd7OFUZXVtN2AaMJgsz09rp0ZgDjAsU1O1YaJZRDoBE4EfAx2BD4HvqurDCcToCpAnXZc1EekM/AT4AdAByAAXqOrj2/q+kHgfA4YS70kNDdhIe+SmCXdTIrI39gZyWGj6A3Cpqi6JJ0RXqHx6wWVFRI4AXgWqsd+n24B9Py/hAoSEdww2Io5rjrch3O/YrSVcAFV9EzgCmwqpB84CZovI2SKSbydhuBTxka5rFxHpDlwLjMOOt3kLGKOq/2zP9Sqra4cBfwQqyM2otwFYDozK1FRNa8s3isjuwD3AiND0N2zKYUG0Ibpi4CNd12YiMhJbBvY97Hj1XwJD25twAUIiHAhMwuZbo9oyXB+uNwkY2NaEC6Cq84HjsKI9K4GTgFkicqGIeB9ybeIjXbfdRGQH4GbgO6FpOja6fS3K+1RW11YAo4EJQA+gnLYNEFqwZFuH1XyYEtVOMxHpC9wJnBqangbOV9V3ori+K3yedN12EZEzgDuAnbGR40+Bm1W1OVf3rKyuLcE+0p8AHAkMwRJqMzalIVidXsXKlJYAs7B6uI8AT+WieE2Y0z0DW4Pc+vP4MfAfufx5uMLgSddtk4j0wZLL10LTVGCsqsZ+hlhIwrsDg7B53zLs1N4G7EyzeZmaqth+oUVkR+AW4Fuh6WVs5B9L4V+Xnzzpui0Ko7nR2HRCL2A1tiTsblX10oebEJETgLuB/tgo/FrgWlVNZ3UflyhPum4zIlKJPa0/LjT9HbhIVd9PLKiUE5EeQA1wcWiahY16X0guKpdG/uTVbSAiHUTkEmxlwnHAUuAcoMoT7rapap2qjsPmnt/G5p//KSI3i0jXZKNzaeIjXQeAiOyF7cD6cmj6I3CJqn6cXFT5SUS6YDv0rsR26L2LrXB4MtHAXCp40i1yItIRm6v9CdAJ+Ahb+P/XRAMrACJyEPZGtn9oug+YoKorEgvKJc6TbhELSeG3wH6haRJwpSeF6IQ3tSuxJXb+puY86Raj8PH3p9jmgw7AfKxAjX/8zZEwfTMJODw0/Qmbvlm89e9yhcgfpBUZETkSq3U7EdtccDOwnyfc3FLV2cBw4BJgDXAmtpX4HC+gU1x8pFsktrKk6TxVfTG5qIqTL8krbj7SLQIiciK2DOxibPH+NcCBnnCToaoZYCRwLrAC2+b8pohc7AV0Cp+PdAuYiOyEbVM9JzS9jI1uX08uKrcpEdkVq2mR+DZrFw9/Vy1AYs7EphDOwQqyTAC+7Ak3XVR1kaqejhXQWYzN+84UkYkiUppsdC4XfKRbYLz0YP4KpTNvwmpeALyCfTKJtHSmS5aPdAtEGN2OwUa3p2K1ZC8ERnjCzQ+qukxVz8Xme98DDgReFpFfhnPoXAHwkW4BCMfJ3AscG5r8OJk8JyLdsGpl3yOC45BcevhIN4+FAjXjgdexhPsJcDZwiifc/Kaqq1X1EmyOdw6wJzBNRG4NCdnlKR/p5qktHBF+P3CZHxFeeMLUwo+xDS0dsKmHC1T1sUQDc+3iSTfPiEgn4IfA1UBH4ENsKuHhRANzOSciQ7FaGQeEpinA5aoayflvLh6edPOIiByCjW73DU13AxNVdWVyUbk4hQI6l2MbXMqARcA4Vf1LooG57eZJNw+ISDnWyS7H5uHnYQvon04yLpccERmMFdAZFpr+DHxPVRclF5XbHv4gLeVE5GisQM2E0HQjVqDm6YRCcimgqnOAo4Bx2Pl1p2MFdL7jBXTSzUe6KSUiPYHrsbW2YCsUxqjqS8lF5dJIRL4A3AV8NTQ9BlwYajy4lPGRbgqJyEnAm1jCbcJq3x7sCddtiaq+B5wIfBtYBhwPvCEi3/cCOunjI90UEZHewK3AWaHpRWx0+2ZyUbl8IiK7AP8JfD00PYfN/7+VXFRuU/4umAJhC+9Z2Bbes4B6YDxwhCdc1xaqulhVz8Sqli0CjgBeE5GrwsoHlzAf6SZMRPoBvwFOCk1PYgvf5ycXlSsEIlIB/BoYE5pexQrozEgsKOcj3aSISImIXIDN3Z4ErATGAsd5wnVRUNXlqjoWO6EiAwwFXhKRmnBOnkuAj3QTICJ7YAVqjg5NfwUuVtWFiQXlCpqIdAV+CVyKFdCZiz0vmJZoYEXIR7oxEpFSEZmALf86GlgCjAL+3ROuyyVVXaOq47E53tnAIGCqiNwuIt2Tja64+Eg3JiKyL7aF95DQ9DtgvKouTS4qV4xEpAz4EVANlALvY+t6/5FoYEXCk26OhV/wq8KfUuAD7Bf874kG5oqeiOyHFdA5KDT9F1ZAxwcCOVRQSbeyurYEGIB9dOoCdALWAQ3YHNa8TE1VS1zxiMhh2Oh279B0J1CtqnVxxeDctoRz2MYDPwc6Ax9jW4v/rDEmh7T13VzK66QbXqgRQBVW7HkvoAU7ZlzCHw1/SrE57NnYiau1wJO5eCHDQ4tfAJeFGN7GFqg/G/W9nIuCiAzECugcGZr+G6te9lEu7pfWvhuHvEy6ldW1FcC5WBGY7kBX7EXaXgqswc4RuwmYnKmpiqQmqYiMwFYmfBFYjxWouUZVG6K4vnO5ErYMXwDcgPWrlVhlu8lRjXrT3HfjkldJt7K6thwrAjMWe1csj+Cy9di76CRgYqamqr49FxGRXthC9LGh6TVsSc70CGJ0LjYi0h8roHNiaHoC27Dzbnuvmea+G7e8SbqV1bXDgQeACmzOJ2oNwHJgVKamqk1rF0XkVGxXWR9sHurnwA2q2hR5lM7FIJSHPAu4DdgRS3BXAber6vq2XCvNfTcJqU+6ldW1ZcAtwGhy84J9VgN2DMr4TE3V2m19oYjsjP1SjgpNz2Oj29k5jdC5mIQiTLcB3whNz2PPJ2Z93vemue8mKdVJt7K6thtWG3Qo8bxorRqAGcDITE3V6s/+YxgFfBOrCLYDNsdUDdzZ1lGAc/lARE7BPs31xT7N/QK4fmuf5tLad9MgtUk3vGjTgMHYUpa4NWJHXw/b9MXbwnzX49h8Vyb2CJ2LUSis/2vg/NA0E/tk9/KmX5fWvpsWqdwGHD6WPEZyLxrhvoOBRyura8tCgZrvYuUXTwRWYE9hR3rCdcVAVVeq6gXYUq/5wH7AiyJyQ2sBnTT23YRi2KpUJl1sHmgoyb1orToDBzSvXnYf8DS2uaEbtoZxiKpOiXMBuXNpoKpPYSdS3xyargRmishRpKzvsjHG1Ehd0g1POkcT7zzQtnQpKev6zbJ+Q4YDi4EzVPVruVo07lw+UNV6Vb0COBwrT7pHWb+9n9b1TeeTor4LnFtZXTvsc78yRqma0w1r+d7GJutTZX3DqoblT9wzcPUbT32YdCzOpYmIdCrp0v0nfc67/Uel3XdMOpwtWQgMTMs63rSNdG/A1vKlTocu3dnp5CsmJh2Hc2mjquv6X/qHXh26VjQmHctWVADXJR1Eq9SMdMP2wIUkPxe0LY1A33zbduhcLnnfbZs0jXTPxbYHplkLNt/snNvI+24bpGKkGyoOLcC20bZLj86lHDdkFw6t3JG9+/agd/cyKso7sbZ5PZml9Tz11sf89rl3WdmQ9c7chUD/fK1w5FyUoui7AL3KO3L+sN0ZsdfO9K+wsgwfLK/nydkfc8/U+VH0W0hJ3y1N8uabGIFVHGq3I/bYiZu+PnSz9k6lJey7W0/23a0n3zikP2dPeoF5S9Zkc6sewLFYERDnil3WfXfQLt343XmHsUuPT89O7LlrD/bctQdnHNSPb/32ReYuznqfQyr6blqmF6qwEm9Zq2to4uHXFnLT43O459n5LK7bOLe/S4/OXHvavtneopyNu9GcK3ZZ9d2y0hLuOuegDQl3ZUMTdz0zj7uembdhdLtLj8785psHUVaadbpKRd9Ny0h3OG2rqbmZFfVNXPPwm/zhpfdpbNr46eGuZ+fx6KVH0ru7bUw5pHIHunbqwJp17S6RUMLGQs/OFbus+u5pQ3dj9526bfj7pQ/M4Om5SwB44d2lTBl9KAADenfj1KG78aeXP8gm1lT03cRHumFOaEi213l+/lIm/zPzqYQLsGzNOl7KLNvw95ISoWP275hDKqtrs3qTcC7fRdF3R+6964b/rmts2pBwAZ6Zu4RVjRvncr+6yddmIfG+m3jSxc5FymllrgG9N76TZpauYUV91pPyLVjczhWzrPvukD49Nvz3gmWf3rugCguWbzxwZa8+kZwUn3jfTUPSHYSdi5QTl44YyOBdN75YNz8+N4rLNmNxO1fMsu67FeUdN/z3qrWbX2pV48a2Hco7ZXOrVon33TTM6XYhy/ncLRGBH524F2OH7b6h7T+emMv/vLYwksuTnv3lziUl0r4rW7iURD8RkHjfTUPS7UTESbdrpw7cdtYBjNhzFwBaWpSaf7zFvVPnR3ULAVJXMs65mGXdd5fXN7Frzw4AdO+8eTrqVraxbVn9umxu1SrxvpuGpLsOO+EzErv16sKkbx/MXmGuqH5dM+P/9BqPvrkoqluAxZva40Cci0nWfXfWR3Xs2tOWi/Wr6IKIzeWCjXL777Dx/MrZH63K5latEu+7aZjTbSCipHtA/148dPHhGxLuwhUNfP2u56NOuGDx+pHqrthl3Xcfm7Wxb3bv3JGjB+284e9HD9r5UyPdiPpx4n03DSPduUQQx4H/VsH9Yw+jc0f7qNK8voW/zfyIw/fYicP32OlTX/u3mQv5aGVWBZFKsbidK2ZZ993/nvEhFxy5+4a1ureOGsr9/3ofgLMO/bcNXzf/k9U89GokVVUT77tpSLrziGDEvftOXTckXIDSDiVccOTuW/za1xesyDbplmBxO1fMsu67a5tbuOj30/n9eYexc4/O9OjSkYuO+vSKro/rGrno99NZ2xxJyYTE+27i0wuh+ES+HVk+K1NTlXylIOcSFFXfnbt4Ncff+ix3Pv0Ocxevon5dM/Xrmpm7eBV3Pv0Ox9/6bBR1F1ol3nfTMNIFmIqdZ9TuJ6EPvrKAB19ZEF1EW9cCPBvHjZzLA1n3XbBt/Dc8OocbHp0TTVRbloq+m/hIN6gFsir9FaN64JGkg3AuJbzvtlFaku6TQCTrQWJQBzyVdBDOpYT33TZKRdINc0M3Yu9EaVYP3Jh0EWTn0sL7btulIukGk0lXPFtSAkxJOgjnUsb7bhuk5gcVDoybREo3Hej65iZtWX9fGg62cy5N3rvupBVrF73zTEvT2rSu6GkA7k1L301N0g0mAqn4wXzW+voVHT+4ZdThIjI06VicSwsR6Qs8tPj3E0e2NK5Oa43pZcAPkw6iVaqSbqamqh4YRcpGu9rSsvaTh29apE2NBwAvi8ivRCTNx007l1NixgKzgFO0eW1d3Yt/vkFVU9V3sVwyKuSWVEhV0gXI1FRNw+Ze0vLiNUhJyX1r3399IHAb9jO7CnhVRI5INjTn4iciA7BVC/cCPYGHgSF1L/11oohMIUV9F5icqal6LulANpW6pBuMB2YAWe3VjUBjiONyVV2tqpdiZ0K9BQwGporIbSLSbVsXca4QiEgHEbkceB04BvgEOAs4VVVbCyOkru8mHMdmRDWdc9+V1bXdgGlYckvio3wjMAcYlqmp+tQexDC1cDU2B10KvAdcoKqPxR6lczEQkX2A+4BDQ9P/BS5T1U8++7Vp7rtpkNaRLuGHNQx7t4r740oD8ApbedFUtVFVrwYOCV/3BeBREZksIjvEG6pzuSMinUTkp9jv+aHAAuAkVT1nSwkX0t130yC1SRc2vHjHYOsA43rxGsL9jv28F01VXwUOw56MrgVGA7NE5PQcx+hczonIIcB04GdAR+AuYG9Vrf287017301SaqcXPquyunYY8EeggtyccdSALVcbFR7mtYmIDMLWGQ8PTX8GvqeqkVdQdy6XRKQc+Dk2P1sCvAOMVdVn2nO9tPfduKV6pLup8MMciCW2RqLbdlgfrjcJGNjeF01V5wJHA+OA1cDpwGwRGS2Sg+P1nMsBETkGe1B2RWj6NbB/exMupL/vxi1vRrqbqqyurcA+yk8AegDltO0NpAV7weqwfeNTotytIiL/BtwNfDU0PY49aMtEdQ/noiQiPYEbgAtC0+vAear6cpT3SXvfjUNeJt1WldW1JcAI4ATgSGAI9qI0Y/U9BTsTSbFVBiXYYu5nsRJvT+WqAEYY3X4TuBXYASt/Vw3coaqJF91wrpWInIzN1/YFmoBfANeraiTH725JmvturuV10v2s8ELuDgzC5o7KsAdcDdi5SPPirhovIjsD/wmcGZr+ic2P5dtpGa7AiEhvbFBwVmh6ARijqrPijiWNfTdXCirpppmInAbcCfTBjq6+Bvi1qjYlGZcrPuFT2FnYDssdsY/rVwG3q+r6JGMrBp50YyQivbB5qDGh6TVs3uyVxIJyRUVE+gO/AapC05PY84b5yUVVXPJm9UIhUNUVqjoW+ArwLrA/8C8RuU5EcrGUxjkARKRERC4E3sQS7krszf84T7jx8pFuQkSkK/bA4jLsocFcbK53apJxucIjIgOx4jRHhaaHgHGqujCxoIqYj3QToqprVPVy4HDsqewg4FkRuUNEuicbnSsEIlIqIhOAmVjC/Rh7oPs1T7jJ8ZFuCohIGfYg4ypsecwHwIWq+vdEA3N5S0T2wwrUHBya/gurlrc0uagceNJNlS10lN8B472juO0V3sB/hK0J9zfwFPKkmzIiUorN8/4CK4u3BPge8P/UXyy3DSLyJexNe0hougOoVtV8OSK9KHjSTSkR2QPbU+4PP9w2hYeyvwQuxR7Kvo1tcvCHsinkD9JSSlXfAY4FLgJWAadhZSPHeAEd10pERmB1Ei7DttFehxWo8YSbUj7SzQMi0g/bG+8L2h2wxY02r2KjW99ok3I+0s0DqroAOBk4GzuXagTwuohcJiIdEg3OxU5ETsWWGY7BtpT/CDjUE25+8JFunklTkRIXLxHZBauXsGnxpDGq+lZyUbm28pFunlHVJap6NnAK8CHwJew4+B+LSKdko3O5IOZb2Oj2TKxM6CXAcE+4+cdHunlsK4Wnx6jqS8lF5aIUCuLfhdWdBS+In/d8pJvHVHWlql6IrXKYB+wLvCAiN4RzrlyeCgVqLsYK1JyAnQE2GhjpCTe/+Ui3QIQkew1wOREcJuiS44ecFjZPugVGRA7FdiXtE5ruAiaqal1yUbntEXYjXoG9eZYBi7ENMX9ONDAXKU+6BSg8UPshcDXQEVgAXKSqtYkG5rZKRIZib5YHhqYpwBWquiypmFxueNItYCKyD9aRDw1N9wOXqeqS5KJymxKRzsCPgYlAB+A97EHZY4kG5nLGH6QVMFV9A6vXezl2wN/Z2Fbib/hW4uSJyOHADKykZwl2gOk+nnALm490i4SIDADuwVY6ADwMfFdVP0wuquIkIt2Aa7HqcQK8hT30fC7RwFwsfKRbJFR1HnY22/lAHbateJaInO+j3viIyPHAG8D3sQI1vwIO8IRbPHykW4REZDfsOPhTQtP/YvOI7yQXVWETkR2Am7C1tmDTCuep6qtJxeSS4SPdIhSmFE4DvoEVST8GmCkiV3gBneiJyOnYFt7RwFpsZcmhnnCLk490i5yI7ATcApwTml7CRmBvJBdVYRCRXYHbgdND0zRs7nZOclG5pPlIt8ip6ieq+i3gJGw97yHAKyLyMy+g0z6hQM1obHR7OrAaGAcc5QnX+UjXbSAiPbCTB74bmt7ERr3/Si6q/CIilcDdwPGh6R/YwZDvJxaUSxUf6boNVLVOVS/GzmV7G9gbeF5EbvICOtsWCtR8H1uZcDywDPg2cKInXLcpH+m6LRKRLsDPgAnYm/N84HxVfSrJuNJIRPbECtQcEZr+BFyiqouTi8qllSddt00icjC2lXi/0DQJuFJVVyQWVEqISEfgSuCnQCdgEbbh5KEk43Lp5knXfa6QXCZiNQI6AQux5PI/ccZRWV1bAgwABgFdQizrsC3Oc4F5mZqqljhiEZEDsTejoaHpPuzNaHkc93f5y5Ou224iMgQb6X45NP0R+xj9cS7uF5LsCOwU5OHAXtgurmZs+6wAGv6UYtMgs4GpQC3wZNRJOEy7/AQb4XYA3sU2ljwR5X1c4fKk69okbJ4YB9QA5cBS4FLgfo3ol6myurYCOBebT+4OdMUS7PZS7ByxOmwX2ORMTVXWI1ARGYaNaAeFe9wKXK2qa7K9tisennRdu4jIF7ECOl8JTbXYlMMH7b1mZXVtOXA9MBYb0UaxYqIeGwFPAiZmaqrq23oBEemOvcmMC02zsLPoXoggPldkPOm6dguFckYDNwO9gFXAD4B7VLVNH+srq2uHAw8AFdh8bdQasHPGRmVqqqZt7zeJyAnYutv+2LRGDfArVV2bgxhdEfCk67ImIn2AO4B/D03PYttd3/68762sri3DtiGPJjfJ9rMasFMZxmdqqraaOEVkxxDXt0LTdGyjyMycR+gKmiddF4kw6j0dS747A43YUqqbVbV5S99TWV3bDXgMWwEQR8Jt1YBV+RqZqalavek/hP+PM7CaCa3/Hz8Bbtna/4dzbeFJ10UqjBBvAr4TmqZj85+vbfp1IeFOAwYDnWMN0jQCc4BhrYk3jNjvxCqwATyDbQj53BG7c9vLtwG7SKnqUlUdDXwVeB84CHhZRH4hImWwYUrhMZJLuIT7DgYe7Xfx5DIROQ9bbnYaNjd9EXCsJ1wXNU+6LidU9VHsGPjbsTW0VwMzROTL2FzpUJJLuK06q7YcuPbDt97BloL1xFZhDFHVu9v6MNC57eFJ1+WMqq5S1e9jGxvmAHuV9dv7OV3ffD7xzuFulUhJ5y4DD+tX1n+flcA3gZNVdUHScbnC5XO6LhYi0rmkc7ef9xlzx5Wl3XdMOpzNaEvLIikpGdCedbzOtYWPdF0sVLWx/2UPlHfoWpHK9a1SUtITqyXsXE75SNfFImztXUjy87jb0gj0jWLLsHNb4yNdF5dzsa29adbCxtN6ncsJH+m6nAvVwhYAfdp7jfFfGcjefXuyx87dqCjvRNdOHWhoWs+HKxp4ObOc373wHnMWr4oi3IVA/7hKRLriU5p0AK4ojMCqhbXbpSMGbdbWvUMJe+7akT137cGZB/dn3P2v8PjsrA9r6AEcC3ipRpcTnnRdHKqw8ozttmTVWl5+bxnvL6tnZX0T5WWlDB+4E/v36wVAp9ISfjBycBRJtxw4EU+6Lkc86bo4DKdt9XA3c8i1m+fAmx6fwxPjj2JA724A9N8hkrMzS4Ajo7iQc1viD9JcToX53CFRXlMEepV35OT9+rJbr417LN5aFMmcLsCQyurarN4knNsaH+m6XBsArI/iQv16dWHaxGO3+G/L1qzjmoffjOI2YKsYBgDvRHVB51r5SNfl2iCs+HfOvL14FWfd+wIzPlgR1SWbsbidi5wnXZdrXchyPrfVioYmfvXIbK7/x1v89rl3ySy1o8kG7tKdv447glP27xvFbcDiTUVtCFd4fHrB5VonIkq6q9c2c+/U+Rv+/qtHZvN/zj2UYXvsROeOHbjua/vy/LylLFmd9U5jAcqyvYhzW+IjXZdr67CTcyO3vkV5cpMlYuWdShnav1cUl1YglTUiXP7zpOtyrYEsk+6hlTvQs0vHzdpF4OjBvT/VptHkd8Xidi5yPr3gcm0uWf6enXlwP07evy8vzl/GmwtXUtfYTEV5J44Z3JuBu2zc6FbX2MSL85dlGy9YvHOjuJBzn+VJ1+XaPCL4RFVW2oEjB/XmyEG9t/jvqxqbuOQPM1i1NpKFEiVY3M5FzgveuJyrrK6dDhzY3u8/pLKCE/ftwwH9K+jTszO9ym2qoa6hiflL1jBt3if84V/v88nqdVGFPD1TU3VwVBdzblM+0nVxmAocQDtXMbyUWc5LmdhK3LYAz8Z1M1d8/EGai0MtsCbpILZTPfBI0kG4wuVJ18XhSexY83xQBzyVdBCucHnSdTkXCoLfiI0i06weuNELmLtc8qTr4jKZ9P++lQBTkg7CFba0dwJXIMJhj5NI76aDBuBeP5TS5ZonXReniUBak9oy4IdJB+EKnyddF5tMTVU9MIr0jXYbgFEhPudyypOui1WmpmoaNm+alsTbAEzO1FQ9l3Qgrjh40nVJGA/MABoTjqMxxHF5wnG4IuLbgF0iKqtruwHTgMFA5wRCaATmAMMyNVWrE7i/K1I+0nWJCIluGDbSjHuqoQF4BU+4LgGedF1iQsI7BlvDG1fibQj3O9YTrkuCTy+4VKisrh0G/BGoIDfnkzVgy9VGhYd5ziXCR7ouFUIiHIhtoGgkui3D9eF6k4CBnnBd0nyk61Knsrq2AhgNTAB6AOW0bYDQgiXbOqzmwxTfaebSwpOuS63K6toSYARwAnAkMARLqM1YbV7BzjNTrDZ0CTALq4f7CPCUF69xaeNJ1+WNkIR3BwZh875l2Km9DdiZZvMyNVX+C+1SzZOuc87FyB+kOedcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjDzpOudcjP4/hQKfvCjES0EAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# n 是图 G 的顶点数，同时也是量子比特的个数\n",
    "n = 4\n",
    "G = nx.Graph()\n",
    "V = range(n)\n",
    "G.add_nodes_from(V)\n",
    "E = [(0, 1), (1, 2), (2, 3), (3, 0)]\n",
    "G.add_edges_from(E)\n",
    "\n",
    "# 将生成的图 G 打印出来\n",
    "pos = nx.circular_layout(G)\n",
    "options = {\n",
    "    \"with_labels\": True,\n",
    "    \"font_size\": 20,\n",
    "    \"font_weight\": \"bold\",\n",
    "    \"font_color\": \"white\",\n",
    "    \"node_size\": 2000,\n",
    "    \"width\": 2\n",
    "}\n",
    "nx.draw_networkx(G, pos, **options)\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 编码哈密顿量\n",
    "\n",
    "量桨中，哈密顿量可以以 `list` 的形式输入。这里我们构建式（11）中的哈密顿量 $H_D$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.426170Z",
     "start_time": "2021-04-30T09:11:08.418352Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1.0, 'z0,z1'], [-1.0, 'z1,z2'], [-1.0, 'z2,z3'], [-1.0, 'z3,z0']]\n"
     ]
    }
   ],
   "source": [
    "# 以 list 的形式构建哈密顿量 H_D\n",
    "H_D_list = []\n",
    "for (u, v) in E:\n",
    "    H_D_list.append([-1.0, 'z'+str(u) + ',z' + str(v)])\n",
    "print(H_D_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，在这个例子中，哈密顿量 $H_D$ 为\n",
    "\n",
    "$$\n",
    "H_D = -Z_0Z_1 - Z_1Z_2 - Z_2Z_3 - Z_3Z_0.\n",
    "\\tag{12}\n",
    "$$\n",
    "\n",
    "我们可以查看哈密顿量 $H_D$ 的矩阵形式，并且获取它的本征值信息："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:08.792299Z",
     "start_time": "2021-04-30T09:11:08.777145Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4.  0.  0.  0.  0.  4.  0.  0.  0.  0.  4.  0.  0.  0.  0. -4.]\n",
      "H_max: 4.0\n"
     ]
    }
   ],
   "source": [
    "# 将哈密顿量 H_D 从 list 形式转为矩阵形式\n",
    "H_D_matrix = pauli_str_to_matrix(H_D_list, n)\n",
    "# 取出 H_D 对角线上的元素\n",
    "H_D_diag = np.diag(H_D_matrix).real\n",
    "# 获取 H_D 的最大本征值\n",
    "H_max = np.max(H_D_diag)\n",
    "\n",
    "print(H_D_diag)\n",
    "print('H_max:', H_max)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 搭建 QAOA 电路\n",
    "\n",
    "前面我们介绍了 QAOA 需要将两个酉变换 $U_C(\\gamma)$ 和 $U_B(\\beta)$ 交替地作用在初始态 $|s\\rangle = |+\\rangle^{\\otimes n}$ 上。在这里，我们使用量桨中提供的量子门和量子电路模板搭建出一个量子电路来实现这一步骤。要注意的是，在最大割问题中，我们将最大化哈密顿量 $H_C$ 的期望值的问题简化为了最大化哈密顿量 $H_D$ 的期望值的问题，因此要用到的酉变换也就变成了 $U_D(\\gamma)$ 和 $U_B(\\beta)$。通过交替地摆放两个参数可调的电路模块，我们得以搭建QAOA电路\n",
    "\n",
    "$$\n",
    "U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1),\n",
    "\\tag{13}\n",
    "$$\n",
    "\n",
    "其中，$U_D(\\gamma) = e^{-i\\gamma H_D}$ 可以由下图中的电路搭建实现。另一个酉变换 $U_B(\\beta)$ 则等价于在每个量子比特上作用一个 $R_x$ 门。\n",
    "\n",
    "![U_D circuit](figures/maxcut-fig-cir_ud.png \"图 3：酉变换 $e^{i\\gamma Z\\otimes Z}$ 的量子电路实现\")\n",
    "<div style=\"text-align:center\">图 3：酉变换 $e^{i\\gamma Z\\otimes Z}$ 的量子电路实现 </div>\n",
    "\n",
    "\n",
    "因此，实现一层酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路如图 4 所示。\n",
    "\n",
    "![U_BU_D circuit](figures/maxcut-fig-cir_ubud.png \"图 4：酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路实现\")\n",
    "<div style=\"text-align:center\">图 4：酉变换 $U_B(\\beta)U_D(\\gamma)$ 的量子电路实现 </div>\n",
    "\n",
    "量桨中，电路运行前每个量子比特默认的初始状态为 $|0\\rangle$（可以通过输入参数来自定义初始状态），我们可以通过添加一层 Hadamard 门使每个量子比特的状态由 $|0\\rangle$ 变为 $|+\\rangle$，由此得到 QAOA 要求的初始态 $|s\\rangle = |+\\rangle^{\\otimes n}$。在量桨中，可以通过调用 `superposition_layer()` 在量子电路中添加一层 Hadamard 门。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:10.245237Z",
     "start_time": "2021-04-30T09:11:10.238838Z"
    }
   },
   "outputs": [],
   "source": [
    "def circuit_QAOA(p, gamma, beta):\n",
    "    # 初始化 n 个量子比特的量子电路\n",
    "    cir = UAnsatz(n)\n",
    "    # 制备量子态 |s>\n",
    "    cir.superposition_layer()\n",
    "    # 搭建 p 层电路\n",
    "    for layer in range(p):\n",
    "        # 搭建 U_D 的电路\n",
    "        for (u, v) in E:\n",
    "            cir.cnot([u, v])\n",
    "            cir.rz(gamma[layer], v)\n",
    "            cir.cnot([u, v])\n",
    "\n",
    "        # 搭建 U_B 的电路，即添加一层 R_x 门\n",
    "        for v in V:\n",
    "            cir.rx(beta[layer], v)\n",
    "\n",
    "    return cir"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搭建 QAOA 量子电路的工作完成后，如果运行该量子电路，得到的输出态为\n",
    "\n",
    "$$\n",
    "|\\vec{\\gamma},\\vec{\\beta}\\rangle = U_B(\\beta_p)U_D(\\gamma_p)\\cdots U_B(\\beta_1)U_D(\\gamma_1)|s\\rangle.\n",
    "\\tag{14}\n",
    "$$\n",
    "\n",
    "### 计算损失函数\n",
    "\n",
    "由上一步搭建的电路的输出态，我们可以计算最大割问题的目标函数\n",
    "\n",
    "$$\n",
    "F_p(\\vec{\\gamma},\\vec{\\beta}) = \\langle\\vec{\\gamma},\\vec{\\beta}|H_D|\\vec{\\gamma},\\vec{\\beta}\\rangle.\n",
    "\\tag{15}\n",
    "$$\n",
    "\n",
    "要最大化该目标函数等价于最小化 $-F_p$。因此我们定义 $L(\\vec{\\gamma},\\vec{\\beta}) = -F_p(\\vec{\\gamma},\\vec{\\beta})$ 为损失函数，即要最小化的函数，然后利用经典的优化算法寻找最优参数 $\\vec{\\gamma},\\vec{\\beta}$。下面的代码给出了通过量桨和飞桨搭建的完整 QAOA 网络："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:11.218109Z",
     "start_time": "2021-04-30T09:11:11.206471Z"
    }
   },
   "outputs": [],
   "source": [
    "class Net(paddle.nn.Layer):\n",
    "    def __init__(\n",
    "        self,\n",
    "        p,\n",
    "        dtype=\"float64\",\n",
    "    ):\n",
    "        super(Net, self).__init__()\n",
    "\n",
    "        self.p = p\n",
    "        self.gamma = self.create_parameter(shape=[self.p], \n",
    "                                           default_initializer=paddle.nn.initializer.Uniform(low=0.0, high=2*np.pi),\n",
    "                                           dtype=dtype, is_bias=False)\n",
    "        self.beta = self.create_parameter(shape=[self.p], \n",
    "                                          default_initializer=paddle.nn.initializer.Uniform(low=0.0, high=2*np.pi),\n",
    "                                          dtype=dtype, is_bias=False)\n",
    "\n",
    "    def forward(self):\n",
    "        # 定义 QAOA 的量子电路\n",
    "        cir = circuit_QAOA(self.p, self.gamma, self.beta)\n",
    "        # 运行该量子电路\n",
    "        cir.run_state_vector()\n",
    "        # 计算损失函数\n",
    "        loss = -cir.expecval(H_D_list)\n",
    "\n",
    "        return loss, cir"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练量子神经网络\n",
    "定义好了用于 QAOA 的量子神经网络后，我们使用梯度下降的方法来更新其中的参数，使得式（15）的期望值最大。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:12.968989Z",
     "start_time": "2021-04-30T09:11:12.961264Z"
    }
   },
   "outputs": [],
   "source": [
    "p = 4      # 量子电路的层数\n",
    "ITR = 120  # 训练迭代的次数\n",
    "LR = 0.1   # 基于梯度下降的优化方法的学习率\n",
    "SEED = 1024 #设置全局随机数种子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里，我们在飞桨中优化上面定义的网络。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:54.550338Z",
     "start_time": "2021-04-30T09:11:21.244581Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter: 10   loss: -3.8886\n",
      "iter: 20   loss: -3.9134\n",
      "iter: 30   loss: -3.9659\n",
      "iter: 40   loss: -3.9906\n",
      "iter: 50   loss: -3.9979\n",
      "iter: 60   loss: -3.9993\n",
      "iter: 70   loss: -3.9998\n",
      "iter: 80   loss: -3.9999\n",
      "iter: 90   loss: -4.0000\n",
      "iter: 100   loss: -4.0000\n",
      "iter: 110   loss: -4.0000\n",
      "iter: 120   loss: -4.0000\n",
      "\n",
      "训练后的电路：\n",
      "--H----*-----------------*--------------------------------------------------X----Rz(3.140)----X----Rx(0.824)----*-----------------*--------------------------------------------------X----Rz(0.737)----X----Rx(2.506)----*-----------------*--------------------------------------------------X----Rz(4.999)----X----Rx(4.854)----*-----------------*--------------------------------------------------X----Rz(0.465)----X----Rx(1.900)--\n",
      "       |                 |                                                  |                 |                 |                 |                                                  |                 |                 |                 |                                                  |                 |                 |                 |                                                  |                 |               \n",
      "--H----X----Rz(3.140)----X----*-----------------*---------------------------|-----------------|----Rx(0.824)----X----Rz(0.737)----X----*-----------------*---------------------------|-----------------|----Rx(2.506)----X----Rz(4.999)----X----*-----------------*---------------------------|-----------------|----Rx(4.854)----X----Rz(0.465)----X----*-----------------*---------------------------|-----------------|----Rx(1.900)--\n",
      "                              |                 |                           |                 |                                        |                 |                           |                 |                                        |                 |                           |                 |                                        |                 |                           |                 |               \n",
      "--H---------------------------X----Rz(3.140)----X----*-----------------*----|-----------------|----Rx(0.824)---------------------------X----Rz(0.737)----X----*-----------------*----|-----------------|----Rx(2.506)---------------------------X----Rz(4.999)----X----*-----------------*----|-----------------|----Rx(4.854)---------------------------X----Rz(0.465)----X----*-----------------*----|-----------------|----Rx(1.900)--\n",
      "                                                     |                 |    |                 |                                                               |                 |    |                 |                                                               |                 |    |                 |                                                               |                 |    |                 |               \n",
      "--H--------------------------------------------------X----Rz(3.140)----X----*-----------------*----Rx(0.824)--------------------------------------------------X----Rz(0.737)----X----*-----------------*----Rx(2.506)--------------------------------------------------X----Rz(4.999)----X----*-----------------*----Rx(4.854)--------------------------------------------------X----Rz(0.465)----X----*-----------------*----Rx(1.900)--\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                         \n",
      "优化后的参数 gamma:\n",
      " [3.14046713 0.73681226 4.99897226 0.46481489]\n",
      "优化后的参数 beta:\n",
      " [0.82379898 2.50618308 4.85422542 1.90024859]\n"
     ]
    }
   ],
   "source": [
    "paddle.seed(SEED)\n",
    "\n",
    "net = Net(p)\n",
    "# 使用 Adam 优化器\n",
    "opt = paddle.optimizer.Adam(learning_rate=LR, parameters=net.parameters())\n",
    "# 梯度下降循环\n",
    "for itr in range(1, ITR + 1):\n",
    "    # 运行上面定义的网络\n",
    "    loss, cir = net()\n",
    "    # 计算梯度并优化\n",
    "    loss.backward()\n",
    "    opt.minimize(loss)\n",
    "    opt.clear_grad()\n",
    "    if itr % 10 == 0:\n",
    "        print(\"iter:\", itr, \"  loss:\", \"%.4f\" % loss.numpy())\n",
    "    if itr % ITR == 0:\n",
    "        print(\"\\n训练后的电路：\")\n",
    "        print(cir)\n",
    "\n",
    "gamma_opt = net.gamma.numpy()\n",
    "print(\"优化后的参数 gamma:\\n\", gamma_opt)\n",
    "beta_opt = net.beta.numpy()\n",
    "print(\"优化后的参数 beta:\\n\", beta_opt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解码量子答案\n",
    "当求得损失函数的最小值以及相对应的一组参数 $\\vec{\\gamma}^*,\\vec{\\beta}^*$ 后，我们的任务还没有完成。为了进一步求得 Max-Cut 问题的近似解，需要从 QAOA 输出的量子态 $|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle$ 中解码出经典优化问题的答案。物理上，解码量子态需要对量子态进行测量，然后统计测量结果的概率分布：\n",
    "\n",
    "$$\n",
    "p(z)=|\\langle z|\\vec{\\gamma}^*,\\vec{\\beta}^*\\rangle|^2.\n",
    "\\tag{16}\n",
    "$$\n",
    "\n",
    "通常情况下，某个比特串出现的概率越大，意味着其对应 Max-Cut 问题最优解的可能性越大。\n",
    "\n",
    "Paddle Quantum 提供了查看 QAOA 量子电路输出状态的测量结果概率分布的函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:55.548009Z",
     "start_time": "2021-04-30T09:11:54.556907Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAbM0lEQVR4nO3de9hcZX3u8e+dcBRQQRAtCYbWUMUDqAHZtdsDgg1bDVBROSkqNraSCpe2CluLgnZv1MqubAI1ioh2S/BsqhGwKnZrt5iAKASMpAgSFI0iB2UDRu7+sVZgmMw775r3XWtm8q77c11zZdbpt34TwvxmPetZzyPbREREe80adQIRETFaKQQRES2XQhAR0XIpBBERLZdCEBHRcikEEREtt9WoExjUrrvu6nnz5o06jYiILcqVV175S9u79dq2xRWCefPmsXr16lGnERGxRZF080Tb0jQUEdFyKQQRES2XQhAR0XIpBBERLZdCEBHRcikEEREtl0IQEdFyKQQRES23xT1QFlu2ead8ecrH3nTmi2vMJCI2yRVBRETLpRBERLRco4VA0kJJayWtk3RKj+2vkbRB0tXl6/VN5hMREZtr7B6BpNnAUuAQYD2wStIK29d17Xqx7SVN5REREf01eUVwALDO9o227weWA4c1eL6IiJiCJgvBHsAtHcvry3XdXibpB5I+I2lur0CSFktaLWn1hg0bmsg1IqK1Rn2z+F+AebafDnwVuLDXTraX2V5ge8Fuu/WcVyEiIqaoyUJwK9D5C39Oue5Btn9l+75y8SPAsxrMJyIiemiyEKwC5kvaS9I2wFHAis4dJD2+Y3ERcH2D+URERA+N9RqyvVHSEuBSYDbwUdtrJJ0BrLa9AniTpEXARuB24DVN5RMREb01OsSE7ZXAyq51p3W8PxU4tckcIiKiv1HfLI6IiBHLoHMRLZJB/6KXXBFERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES03KSFQNJzJO1Qvj9O0lmSnlAluKSFktZKWifplD77vUySJS2onnpERNShyhXBecA9kvYF3gL8B/DxyQ6SNBtYChwK7AMcLWmfHvvtBJwEXDFA3hERUZMqhWCjbQOHAefYXgrsVOG4A4B1tm+0fT+wvIzR7d3Ae4F7K+YcERE1qlII7pZ0KvAq4MuSZgFbVzhuD+CWjuX15boHSXomMNf2lyvmGxERNatSCF4J3Ae8zvZtwBzg/dM9cVlQzqJobpps38WSVktavWHDhumeOiIiOkxaCMov/88C25arfgl8vkLsW4G5HctzynWb7AQ8Fbhc0k3AgcCKXjeMbS+zvcD2gt12263CqSMioqoqvYb+AvgM8KFy1R7AFyrEXgXMl7SXpG2Ao4AVmzbavtP2rrbn2Z4HfAdYZHv1YB8hIiKmo0rT0InAc4C7AGzfADx2soNsbwSWAJcC1wOfsr1G0hmSFk095YiIqNNWFfa5z/b9kgCQtBXgKsFtrwRWdq07bYJ9n18lZkRE1KvKFcE3Jf13YHtJhwCfBv6l2bQiImJYqhSCU4ANwDXAGyh+4b+jyaQiImJ4Jm0asv0A8OHyFRERM8yEhUDSp2y/QtI19LgnYPvpjWYWERFD0e+K4KTyz5cMI5GIiBiNCe8R2P5Z+faNtm/ufAFvHE56ERHRtCo3iw/pse7QuhOJiIjR6HeP4K8ofvn/oaQfdGzaCfh204lFRMRw9LtH8EngK8D/pOhCusndtm9vNKuIiBiafoXAtm+SdGL3Bkm7pBhERMwMk10RvAS4kqL7qDq2GfjDBvOKiIghmbAQ2H5J+edew0snIiKGrd/N4mf2O9D2VfWnExERw9avaegDfbYZOKjmXCIiYgT6NQ29YJiJRETEaPRrGjrI9tcl/Xmv7bY/11xaERExLP2ahp4HfB14aY9tBlIIIiJmgH5NQ+8s/3zt8NKJiIhhqzJ5/WMknS3pKklXSvqgpMcMI7mIiGhelUHnllPMUPYy4Mjy/cVNJhUREcNTZfL6x9t+d8fyeyS9sqmEIiJiuKpcEVwm6ShJs8rXK4BLm04sIiKGo1/30bt5aIyhk4F/LjfNAn4D/E3TyUVERPP69RraaZiJRETEaFS5R4CknYH5wHab1tn+t6aSioiI4Zm0EEh6PcVE9nOAq4EDgf9HxhqKiJgRqtwsPgnYH7i5HH/oGcAdTSYVERHDU6UQ3Gv7XgBJ29r+IfDHzaYVERHDUuUewXpJjwa+AHxV0q+Bm5tMKiIihmfSQmD7iPLtuyR9A3gUcEmjWUVExNBU7TX0TOBPKZ4r+Lbt+xvNKiIihqbKoHOnARcCjwF2BS6Q9I4qwSUtlLRW0jpJp/TY/peSrpF0taRvSdpn0A8QERHTU+WK4Fhg344bxmdSdCN9T7+DJM0GlgKHAOuBVZJW2L6uY7dP2v6ncv9FwFnAwkE/RERETF2VXkM/peNBMmBb4NYKxx0ArLN9Y9mUtBw4rHMH23d1LO5A0fQUERFD1G+sof9N8cV8J7BG0lfL5UOA71aIvQdwS8fyeuDZPc5zIvBmYBvykFpExND1axpaXf55JfD5jvWX15mA7aXAUknHAO8Aju/eR9JiYDHAnnvuWefpIyJar9+gcxduei9pG2DvcnGt7d9ViH0rMLdjeQ79m5SWA+dNkMsyYBnAggUL0nwUEVGjKr2Gng/cQHHj91zgR5KeWyH2KmC+pL3KQnIUsKIr9vyOxReX54mIiCGq0mvoA8CLbK8FkLQ3cBHwrH4H2d4oaQnFJDazgY/aXiPpDGC17RXAEkkHA78Dfk2PZqGIiGhWlUKw9aYiAGD7R5K2rhLc9kpgZde60zren1Q10YiIaEaVQnClpI/w0Axlx/LQjeSIiNjCVSkEfwmcCLypXP6/FPcKIiJiBuhbCMqng79v+0kUT/1GRMQM07fXkO3fA2slpfN+RMQMVaVpaGeKJ4u/C/x200rbixrLKiIihqZKIfi7xrOIiIiR6TfW0HYUN4qfCFwDnG9747ASi4iI4eh3j+BCYAFFETiU4sGyiIiYYfo1De1j+2kAks6n2oijERGxhel3RfDgwHJpEoqImLn6XRHsK2nTxDECti+XBdj2IxvPLiIiGtdvGOrZw0wkIiJGo8pUlRERMYOlEEREtFwKQUREy6UQRES0XL8ni+8GJpwfOL2GIiJmhn69hnYCkPRu4GfAJyi6jh4LPH4o2UVEROOqNA0tsn2u7btt32X7POCwphOLiIjhqFIIfivpWEmzJc2SdCwdw1FHRMSWrUohOAZ4BfDz8vXycl1ERMwAk85HYPsm0hQUETFjTXpFIGlvSV+TdG25/HRJ72g+tYiIGIYqTUMfBk6lHI3U9g+Ao5pMKiIihqdKIXiE7e65CDIsdUTEDFGlEPxS0h9RPlwm6UiK5woiImIGqDJ5/YnAMuBJkm4FfkzxUFlERMwAfQuBpNnAG20fLGkHYJbtu4eTWkREDEPfQmD795L+tHyfh8giImagKk1D35O0Avg0HU8U2/5cY1lFRMTQVCkE2wG/Ag7qWGcghSAiYgao8mTxa6caXNJC4IPAbOAjts/s2v5m4PUU3VE3AK+zffNUzxcREYObtBBIuoAe8xLYft0kx80GlgKHAOuBVZJW2L6uY7fvAQts3yPpr4D3Aa8cIP+IiJimKk1DX+p4vx1wBPDTCscdAKyzfSOApOUUYxY9WAhsf6Nj/+8Ax1WIGxERNarSNPTZzmVJFwHfqhB7D+CWjuX1wLP77H8C8JUKcSMiokZVrgi6zQceW2cSko4DFgDPm2D7YmAxwJ577lnnqSMiWq/KPYLuuYtvA95WIfatwNyO5Tnluu74BwNvB55n+75egWwvo3i6mQULFkw4j3JERAyuStPQTlOMvQqYL2kvigJwFF0T2kh6BvAhYKHtX0zxPBERMQ1V5iN4Tjm8BJKOk3SWpCdMdpztjcAS4FLgeuBTttdIOkPSonK39wM7Ap+WdHX54FpERAxRlXsE5wH7StoXeAvwEeDjTNCe38n2SmBl17rTOt4fPFC2ERFRuyrDUG+0bYqun+fYXgpMtbkoIiLGTJUrgrslnUrRx/+5kmYBWzebVkREDEuVK4JXAvcBJ9i+jaL3z/sbzSoiIoamSq+h24CzOpZ/QnGPICIiZoAqvYYOlLRK0m8k3S/p95LuHEZyERHRvCpNQ+cARwM3ANtTjBZ6bpNJRUTE8FQpBNheB8y2/XvbFwALm00rIiKGpUqvoXskbQNcLel9wM+oWEAiImL8VflCf1W53xKKqSrnAi9rMqmIiBieKr2Gbpa0PfB426cPIaeIiBiiKr2GXgpcDVxSLu+XMYEiImaOKk1D76KYbewOANtXA3s1llFERAxVlULwO9vdzw1kToCIiBmiSq+hNZKOAWZLmg+8Cfj3ZtOKiIhhqXJF8NfAUyjGG7oIuAs4ucGcIiJiiKr0GrqHYirJtzefTkREDNuEhWCynkG2F/XbHhERW4Z+VwT/BbiFojnoCkBDySgiIoaqXyF4HHAIxYBzxwBfBi6yvWYYiUVExHBMeLO4HGDuEtvHAwcC64DLJS0ZWnYREdG4vjeLJW0LvJjiqmAecDbw+ebTioiIYel3s/jjwFOBlcDptq8dWlYRETE0/a4IjqMYbfQk4E3Sg/eKBdj2IxvOLSIihmDCQmA7cw5ERLRAvuwjIlouhSAiouVSCCIiWi6FICKi5VIIIiJaLoUgIqLlUggiIlqu0UIgaaGktZLWSTqlx/bnSrpK0kZJRzaZS0RE9NZYIZA0G1gKHArsAxwtaZ+u3X4CvAb4ZFN5REREf1XmLJ6qA4B1tm8EkLQcOAy4btMOtm8qtz3QYB4REdFHk01De1BMbLPJ+nJdRESMkS3iZrGkxZJWS1q9YcOGUacTETGjNFkIbgXmdizPKdcNzPYy2wtsL9htt91qSS4iIgpNFoJVwHxJe0naBjgKWNHg+SIiYgoaKwS2NwJLgEuB64FP2V4j6QxJiwAk7S9pPfBy4EOSMh9yRMSQNdlrCNsrKWY461x3Wsf7VRRNRhERMSJbxM3iiIhoTgpBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMulEEREtFwKQUREy6UQRES0XApBRETLNVoIJC2UtFbSOkmn9Ni+raSLy+1XSJrXZD4REbG5xgqBpNnAUuBQYB/gaEn7dO12AvBr208E/hfw3qbyiYiI3pq8IjgAWGf7Rtv3A8uBw7r2OQy4sHz/GeCFktRgThER0WWrBmPvAdzSsbweePZE+9jeKOlO4DHALzt3krQYWFwu/kbS2kYyhl27zz0mseqOt0XG0uDXi1vk5xxhrL7x8vc/lHh159bpCRNtaLIQ1Mb2MmBZ0+eRtNr2gnGLVXe8NsSqO14bYtUdrw2x6o5Xd25VNdk0dCswt2N5Trmu5z6StgIeBfyqwZwiIqJLk4VgFTBf0l6StgGOAlZ07bMCOL58fyTwddtuMKeIiOjSWNNQ2ea/BLgUmA181PYaSWcAq22vAM4HPiFpHXA7RbEYpTqbn+puyhrX3MY1Vt3x2hCr7nhtiFV3vMabwHtRfoBHRLRbniyOiGi5FIKIiJZLIYiIaLkUgoiIltsiHihrSjmcxQEUTzhD8VzDd+vswirpSbZ/OOAxjwIWduV1qe07aszrENtfncJxY5mbpCdRDFnSmdcK29fXmNdrbV9QV7yIcdHaXkOSXgScC9zAQw+6zQGeCLzR9mU1necntvccYP9XA+8ELuvK6xDgdNsfH0Ve45ybpLcBR1OMZ7W+I6+jgOW2zxxFXh3HjWXxLI8bywI6jLymkdufAYd35fZF25fUmNdpts+oK96k52txIbgeONT2TV3r9wJW2n7yALHOnmgTcLztRw4Qay3w7O4vCUk7A1fY3nuAWN0P8HXmdZDtHarGGufcJP0IeIrt33Wt3wZYY3v+ALF+0CevvW1vWzVWGW8si2d5zFgW0GHlNcXc/hHYG/h4V26vBm6wfdIo8pquNjcNbcVD/yE73QpsPWCs1wJvAe7rse3oAWMJ6FWdHyi3DeK/AscBv+lxjgMGjLXpuHHM7QHgD4Cbu9Y/vtw2iN2BPwN+3SOvfx8wFsDbgWdNVDwpvlAqmaR4PmYKuZ1A7wJ6FrAGqPyFO0kB3X1UeTWQ23/r9YNH0sXAj4DKhUDSXX3y2n7AvKalzYXgo8AqSct5aJTUuRS/Os4fMNYq4Frbm31RSHrXgLH+HrhK0mUdee1J8Qvy3QPG+g5wj+1v9shrKiO4jmtuJwNfk3RDV15PBJYMGOtLwI62r+6R1+UDxoLxLZ6bchjHAlpnXnXndq+k/W2v6lq/P3DvgLHuAPa3/fPuDZJu2Xz35rS2aQignChnEZu3Q143YJxdgHtt31NTXjtT/MPtblPu/oc8dOOam6RZbH7jf5Xt348uK5B0PHAaRdPQZsXT9scGiPUV4H22v9Fj27/Zfu6AuS0EzqG4T7ZZAR2kzVvS+cAFtr/VY9snbR8zirwayO2ZwHnATjzUojAXuBM40faVA8R6D8X3zXd7bHuv7bdVjTVdrS4Em5Rf5Ni+fZxijStJu9PxhdvrF80oYk0Qf0fb3b+ghxprXIsnjHUBHcu8NpH0OB7+7/a2UeYzXa0tBJL2BN4HHERRzQU8Evg6cEr3TeSKsV5Icbk35ViTnOca208bVSxJ+wH/RDFc+HqKzzmH4jO/0fZVA8R6BsUvq0fx8JuoA8ea5Dy13XSbTqwtqXiW5xhpAa27a/e4dhUfRqwq2nyP4GLgH4FjN/3KUDHP8sspeiscOIpYkv58ok3A4wbIqdZYpY8Bb7B9Rdd5DgQuAPYdINYFdcWS9OaJNgE7DpBTrbHKePvRo3hKuoOaiudUYlVwHUVzzNBj9evaLWngrt11x+vjMur7O6sz1qTaXAh2tX1x54ryS3y5pEFvfNYZ62Lg/9D7BuN2I4wFsEP3FzeA7e9IGqgras2x/gfwfmBjj22DPj1fZywY0+JZHjeuBfSDwMETde0GKnftrjveJF3FHz1IUnXGmq42F4IrJZ0LXMjDew0dD3xvhLF+APyD7Wu7N0g6eISxAL4i6csUXR47P+ergUEfpqkz1lXAF3rdqJP0+hHGgvEtnjC+BbTOrt11x6uzq3idsaalzYXg1RT9lU+nq9cQg3cfrTPWycBE/YuPGGEsbL9J0qFs/sTnUtsrRxWL4n+oiaY4HXT+1zpjwfgWTxjfAlpn1+6649XZVbzOWNPS2pvFEcMyQcFbMYWCV3esPwZut72hx7bdB7kJXWes8pgn0/tzDtS1u+54dXYVr7vb+bRyaWshkLQVxa/4w+kaMwQ4v/upxhHEOoLioZqxiFXhXMtsL06siC1PmwvBRRRdFS/k4WOGHA/sYvuVibVZvF0m2gR83/acxNos3qOAUyl+je5OceP+FxTF+MzuoSeGFasr3uHAY2vKbdqxJjnPV2wfWkesuuONa6wq2nyP4FnefMyQ9cB3VAxillib20Dx2H/n0Agulx+bWD19iuJ5khdseuiofBjpNeW2F40oVme853fFO34auU07Vvn0bs9NwH4D5FR7vHGNNV1tLgS3S3o58FnbD8CDTzO+nM3HJEmswo3AC23/pHuDBh8bpQ2xAObZfm/nivKL8kxJrx1hrH7x3ivpdSOMtQr4Jg8vxps8esBYdccb11jTY7uVL2AeRT/7X1CMGvij8v3FwF6J1TPeicC+E2z768TqecxlwFuB3TvW7Q68DfjXUcUa59yAa4H5E2y7ZQqfs7Z44xpruq/W3iOACXsSfNFTmPyiDbHKeLVNGNKSWDsDp5TxNjUt/Zyia/GZHmC8oTpjjXNuko4ErrG92Si0kg63/YWqseqON66xpqu1cxarmPzikxTtv1eUL4CLJJ2SWD3jvZViyAwB3y1fmmJuMz4WgO1f236b7SfZ3qV8PdnFyJKHjyrWOOdm+zO9vhxLOw8Sq+544xpr2oZ5+TFOL4pmkq17rN+GYqahxNpCchvXWBXO9ZNxjDXOueVzNvNq883iOie/aEOscc5tXGOhGmfHqjNW3fHGNVbd8cY11nS1uRCcTH2zWrUh1jjnNq6xoN7ZseqeRnNcc8vnnNrnnLLWFgLbl0jamxomv2hDrHHObVxjleqc+rLuaTTHNbd8zql9zilrda+hiIhoca+hiIgopBBERLRcCkHMaJLmSPqipBsk3SjpHEnbVjiu5xy7ks5QOamPpJMlPWKC/V4i6XuSvi/pOklvKNcfLmmfCuevtF9EHVIIYsaSJOBzFBOmzAfmA9sD75tqTNun2f7XcvFkYLNCIGlrYBnwUtv7As8ALi83Hw5U+YKvul/EtOVmccxYkl4IvNP2czvWPZLiGYG5wJHAAttLym1fopja8/LyiuDDFKNm3gYcZXuDpI9R9Pb4A+AfgLXAL22/oOMcuwA/BJ5g+/93rP+T8tg7y9fLgIOAxRQPrK0DXkUx8mT3fgBLgd2Ae4C/sP3DWv6iovVyRRAz2VOAh02daPsu4CaK5wL62QFYbfspFCNEvrMrztnATymGhH5B17bbKcbYuVnSRZKOlTTLxZSEK4C/tb2f7f8APmd7//LK4XrghAn2W0Yx6N2zgL8Bzh34byNiAq19jiBiEg9QjNIK8M8UTUyV2X69pKcBB1N8cR9CMW9At6dKeg/FsMM7Apd27yBpR+BPgE8XrV0ATHqfI6KqFIKYya6jaP55UNk09DiKJp2n8vCr4u36xBq4DdX2NcA1kj4B/JjeheBjwOG2vy/pNcDze+wzC7jD9n6D5hBRRZqGYib7GvAISa8GkDQb+ABwTtl2fxOwn6RZkuZSPE28ySweKiLHAN/qEf9uYKfulZJ2lPT8jlX78dDYRd3H7AT8rLzBfGyv2GVz1o9VTDKECvv2++ARg0ghiBnLRU+II4Ajy7GDfgU8YPvvy12+TfFL/TrgbOCqjsN/Cxwg6VqKG7pn9DjFMuASSd/oWi/grZLWSroaOJ2HrgaWA39bdi39I+DvKIYH/zbFDWYm2O9Y4ARJ3wfWUIz7H1GL9BqK1ih77VwEHGH7qsn2j2iLFIKIiJZL01BERMulEEREtFwKQUREy6UQRES0XApBRETLpRBERLRcCkFERMv9J2lfuxp4ZulDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 模拟重复测量电路输出态 1024 次\n",
    "prob_measure = cir.measure(plot=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过测量，找到出现几率最高的比特串。 此时，记其在该比特串中对应的比特取值为 $0$ 的顶点属于集合 $S_0$ 以及对应比特取值为 $1$ 的顶点属于集合 $S_1$，这两个顶点集合之间存在的边就是该图的一个可能的最大割方案。\n",
    "\n",
    "下面的代码选取测量结果中出现几率最大的比特串，然后将其映射回经典解，并且画出对应的最大割方案：\n",
    "- 红色顶点属于集合 $S_0$，\n",
    "- 蓝色顶点属于集合 $S_1$，\n",
    "- 虚线表示被割的边。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-04-30T09:11:55.906817Z",
     "start_time": "2021-04-30T09:11:55.625551Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "找到的割的比特串形式： 0101\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAtOklEQVR4nO3dd3hUVf4/8PekT5KhJSGIIewiPbDSFEQUBGkLKlkggAsuEFAjfFlRl2KDXcUV16A/pUmRYiEYKQtrI66AYCEQVBYIRYwgaKIBUpjUmXt+fxxTTSZlyr137vv1PHk29c5HNpn3nHM/5xyTEEKAiIjIIHzULoCIiMiTGHxERGQoDD4iIjIUBh8RERkKg4+IiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGh+KldAJE3s9uB06eBtDTgiy+AgweBrCyguBhQFCAgAAgJAXr2BAYOBHr3lu9bLGpXTuS9TEIIoXYRRN7mu++AV18F1q8Hyv7Crl1z/DOBgUBQEFBQAPTvD8yfDwwfDvhwXobIpRh8RC60Zw/w7LPA4cNytFda2vhrhYYCwcHA3LnA7NnyYyJyHoOPyAWys4EZM4CPPwasVtde22wGmjQBtmwB7rjDtdcmMiIGH5GTduwApk0DCguBkhL3PY7ZDEyaBPy//8fRH5EzGHxEjWS3AzNnAlu3yvtynmA2A82bAwcOAO3aeeYxibwNg4+oEUpLgfHjgZQUz4VeGR8foGlTGX4xMZ59bCJvwOAjaiBFAeLigPffl9ObajCZgGbNgNRUoH17dWog0is2ShM10COPAB9+qF7oAXKJRG4uMGAAcPWqenUQ6RGDj6gBDhwA1qxxfedmYygKkJMDPPig2pUQ6QunOonqqaBATiv+9JPalVQVHAy88w4wapTalRDpA0d8RPX06KNyhKU1BQXAlCmc8iSqLwYfUT2cOQNs2qTufT1HCgqAv/9d7SqI9IHBR1QPL78M2GxqV1G74mK5L6hWg5lISxh8RHWwWuVoz5l9Nz0lOVntCoi0j8FHVIekJNeckHDnncCyZcC+fXIpghAVbwMHOn/9a9eApUudvw6Rt+N5fER1WLmy7iOF6mPWLGDMGOev48j33wNnzwIdOrj3cYj0jCM+IgcUBThxwjXXEgK4dAnYvRt46y3XXLM6X195JBIR1Y7BR+TAmTOAv79rrvXnPwNRUcDddwNr17rmmtVduyZPeiei2jH4iBxIS5P7YrqCJzouhQAOHnT/4xDpGYOPyIHUVNfc3/OkU6fUroBI2xh8RA5kZclRlJ4UFWl7zSGR2hh8RA5oYTPqhvLzk+FHRDVj8BE54Kr7e56m17qJPIHBR+RASIjaFTSczQYEBaldBZF2MfiIHIiKcs2uLZ4UHCzX8xFRzbhzC5EDN98MhIYCeXnOXysuDrjpJvl+mzZVv5aQAIweLd8/fFier9dY3bo1/meJjIDBR+RA796u65AcORKYOrXmr02YUPH+xo2NDz4fH+D22xv3s0RGobNJHCLP+v3v1a6gYUJDgb591a6CSNtMQuhtlRKRZ916K/D552pXUT9BQcDp00B0tNqVEGkXR3xEdZgzB7BY1K6ifv7wB4YeUV0YfER1iI3VR2enxQLMn692FUTap4M/ZyJ1BQQADz4IBAaqXYljfn7y5AcicozBR1QPs2Zpe9RnNsspWT/2aRPVScN/ykTa0aYNMHXqL/Dx8cDZQo0QGHgN8+axT42oPhh8RHWw2WxYunQp1q//PRTlAgBF7ZKqKUBOznCMGTMcFy5cULsYIs1j8BE5kJ6ejltvvRULFixASYkVsbFbEBSknR2gzWaBYcMuIizsNFJSUtCtWzckJSWpXRaRpjH4iGpgt9uxdOlS9OzZE6mpqYiKisIHH3yA7dsXY/FiE4KD1a4Q8PcHoqJM2LmzI06cOIHY2Fjk5+cjIiJC7dKINI0L2IlqYLPZcMstt+DIkSOIj49HYmIimjZtCkAeTDt3LrB2LVBQoE59vr7AddcBaWlAy5b4tS6BI0eO4KayDUEBfPHFF+jXrx9MPKeIqByDj+hXNpsNVqu1POBOnDiBH374ASNGjPjN9wohuyhff93z4efvL0Pvs8/k6RG1+fTTTzFw4EAMGzYMa9euRTRXthMB4FQnEYCKe3l/+ctfUPZaMCYmpsbQA+RBr6+8AixcKJcSeEpwMNClC3DkiOPQA4Dc3Fy0aNECe/bsQbdu3bBu3TrwdS4Rg48Mrqxjs+xeXlpaGjIzM+v1syYT8OSTwN69cpswd973M5lkwD7xhJzerM9tvLvuugsnTpzAmDFjkJ+fj5kzZ2LEiBHs/CTD41QnGVZ6ejqmTp2K1NRUAPjNvbyGKCoCHn8cWL0aKCkB7HbX1RkaCrRtK48q6tq14T8vhEBSUhJmz56NK1euwGKxYMeOHRgyZIjriiTSEQYfGdKLL76IJ598EsXFxYiKisLatWtrndZsiOPHgcREYOtWudOL1dq46/j6yq3SOnUC5s0Dxo93fleWzMxMJCQk4ODBgzh58iS7P8mwONVJhpSZmYni4mLEx8fj+PHjLgk9QJ5+vmEDkJkJPP880K6dbEZp0sTxXp8mk/wesxkICQHuuw9ITQW++gqYNMk1W5G1atUK27dvx1dffVUeeqWlpdi6dSvv/ZGhcMRHhmCz2fD999+jffv2AIDCwkJ8/vnnHpnuy8+XAZaWBuzfD5w/L6dG7XYZhk2bAv37A/36yRPfo6NlEHrCP/7xDyxatIidn2QoDD7yemX38i5duoTjx4+jWbNmapekGe+88w4SEhLK7/0lJiZixowZXPdHXo1TneS1qndsmkwmfP/992qXpSlxcXE4efJk+a4v999/Pzs/yetxxEdeyZUdm0ZQU+dnamoqOnfurHZpRC7H4COvs2bNGsyZM8flHZtGkJWVhYSEBOTl5SElJYVTnuSVONVJXqdNmzZu6dg0gsjISGzbtg3//ve/y0Pvu+++464v5FU44iPds9vtOHDgAAYNGlT+uePHj6Nbt27qFeUlFEXB4MGDsX//fnZ+ktfgiI90rWyPzSFDhuDLL78s/zxDzzVMJhMeeOCBKnt+rl27lqM/0jUGH+mSzWbDCy+8gJ49e+LQoUNo3bo1ioqK1C7L65hMJkyaNImdn+RVONVJulO9Y3P69OlYtmwZOzbdrHrnZ3h4ODIyMhAaGqp2aUQNwuAjXdm5cycmTpzIjk0VlXV+9unTB48//rja5RA1GIOPdCUzMxMxMTGIjY3lujwVCSEghICPj7xb8u677+LKlSuYOXMml0CQ5jH4SNPsdjs2b96MKVOmwO/XnZp//vlntGzZUuXKqMzVq1fRvn17XLlyBUOHDsW6devY+UmaxuYW0qyyjs3p06cjMTGx/PMMPW1p1qwZVqxYgbCwMKSkpLDzkzSPwUeaY7fbq3RsRkVFoUePHmqXRbUwmUyYOHEiTpw4UaXzc/jw4ez8JE3iVCdpSnp6OqZNm4ZDhw4BYMem3gghsHXrVsyePRuXL19Gnz59yjcIJ9IKBh9pxtGjR9G/f392bHqBrKwszJo1C4888gj69++vdjlEVTD4SDMURcEdd9yB9u3bc5TnhR555BF06dKF5/2R6hh8pBqbzYaXX34ZcXFx5V2ARUVFCAoKUrkycrWjR4+id+/eAMA9P0l1bG4hVZR1bP7tb3/DzJkzyzsAGXreqWfPnnj77be55ydpAoOPPKr6qehRUVGYO3cup768XG17frLzk9TAqU7yGJ6KTsBvOz8feOABrF69Wu2yyEAYfOQRV65cQdu2bXHt2jV2bBIA2fn51FNPYenSpWjevDkAGYoc/ZO7MfjIYxYvXoyLFy9ylEc1KioqwqBBgxAfH8/OT3IrBh+5hc1mQ2JiIjp16oQxY8YA4Kt5cmzTpk2YOnUqAHZ+knsx+MjlKt/La9myJb777juEhISoXRZpXPXz/iwWCxITEzn6I5djVye5TE0dm5s2bWLoUb3wtHfyFAYfuUTZurwFCxaguLgY8fHxOH78OBtYqMEiIyOxbdu2Kuv+9u/fr3ZZ5EU41UlOUxQF3bp1Q3p6Ojs2yaWysrKwceNGzJs3r3y6s7CwEGazWeXKSM8YfOQS+/btw5tvvsmOTXKr9PR0DBw4EEuWLOG9P2o0Bh81WFnHZlZWFpYtW6Z2OWQgTz31FJ599lkA7PykxmPwUYNU330lPT0dnTt3VrkqMgp2fpIrsLmF6qWmjs0PPviAoUce5WjPzx9++EHt8kgnOOKjOnGPTdKiyqO/wsJCfPPNN+jQoYPaZZEOMPioTn/5y1+wefNmdmySJmVlZeHIkSMYNWoUABmIWVlZaNWqlcqVkVZxqpNqZLfby99ftmwZHn74Ya7LI02KjIwsDz0AWL9+PTp27Mjz/qhWDD6qwm6344UXXsAtt9yCkpISAEBYWBheeuklTm2SLhw8eJC7vpBDDD4qV7b7yvz583H48GG89957apdE1GAbNmzgae/kEIOPykd5PXv2xKFDh8o7NmNjY9UujajBHHV+Zmdnq10eaQCDz+Aqj/KKi4sxffp03ssjr1B9z8+srCw0adJE7bJIA9jVaXDr1q3DzJkz2bFJXi0rKws5OTno1KkTAODy5cuwWq3c9cWgGHwGlJ+fD4vFAkC2fr/88suYPn06m1fIMO6991785z//4a4vBsWpTgMpu5fXtm1bnD17FoC8HzJ37lyGHhlGSUkJioqK2PlpYAw+g6h8L+/q1avYtWuX2iURqSIgIOA35/2x89NYONXp5ex2OxITE/H000+juLiY9/KIKsnKykJCQgJ27NgBABg+fDj+85//wM/PT+XKyJ044vNiZ86cYccmkQPVOz/bt2/P0DMAjvi8WHp6Onr27ImIiAiO8ojqkJWVhZCQEISGhgIA0tLSEBERwc5PL8Tg8zLnz59HdHR0eZfahx9+iFtuuYXNK0QNYLVa0b17d2RnZ7Pz0wtxqtNLlJ2X16lTJ7z55pvlnx8xYgRDj6iBioqK0KNHD3Z+eikGnxco69hcsGABiouL8fXXX6tdEpGuhYWFsfPTi3GqU8dsNhsSExOxaNEidmwSuUn1zs/JkyfjjTfeULkqcgZHfDp16dKlKqO8+Ph4dmwSuUH1zk9u3q5/HPHpVFFREXr16oX8/HyO8og8JCcnB82aNSv/+O2338aAAQPY+akzDD4dSU9PR6tWrdC8eXMAwOnTp9GqVSs2rxCp4Ouvv8ZNN90Es9nMzk+d4VSnDpR1bPbs2RNz584t/3ynTp0YekQque6663DXXXex81OHGHwaV71j08/PD3a7Xe2yiAyv+r0/dn7qB4NPoyqP8lJTU8tPRV+3bh18fX3VLo+IUPtp708//bTapZEDvMdXWWkpUFQEmEyA2QyoFDBFRUUYNGgQDh06BACIj49HYmIipzWJNEwIgaSkJDzxxBPYt2+f+g0vQgDFxUBJCRAQAAQGyuc2MmjwCQGcOQMcPgx88QVw4ID8uKSkIuxsNiAkBIiJAW6/HejXD+jbF4iK8kiJM2fOxIcffsiOTSKdsdls5RtdK4qChQsXYtasWe4NwoIC+XyWlgbs3w8cOQL89BPg4yPfFEW+tW4N9OkDDBwo/7dPH/ki32CMFXwFBcCWLcDSpcClS/IX4tq1un/Ox0eGYGkp0KMHMH8+MHo04MJd3NPT01FYWIhevXoBkKekK4rCUR6Rjq1cuRKzZs2CxWJxT+fn6dPAyy8DmzfL56PiYvlWl8BA+Wa3A9OmAXPmAB06uK4urRNG8MsvQjz0kBDBwUKEhgohx3yNf7NYhGjRQoh//EOIwkKnSistLRXPP/+8CAwMFB07dhQFBQUu+o8mIrVlZmaK2NhYAUAAEEOHDhXnz593/sIffyzEzTcLYTYL4efn3POZv78QQUFC9O8vxL59ztemA94ffNu3C9G0qRABAc4HXvU3s1mI6GghvvyyUaWdPHlS3HzzzeV/FPHx8SIvL8+1//1EpCpFUcSWLVtEWFiYACAsFotYs2aNUBSl4RfLzRViyhT5It7Vz2dlz2nTpwuRn+/6fwgN8d7gy84W4p573PcLUv2X5eGH6z36qzzKAyCioqLEBx984N5/DyJSVfXR31tvvdWwC3z0kRDh4XJ05u7ns8hIIT75xD3/EBrgnff4Tp0CbrsNyMuTDSueEBwMtG0LfPopEB7u8FtHjRqF999/HwA7NomMRAiBrVu3YvPmzdi1a1f9T3t/5hng+edln4KnmM3A3/8O/O1vnntMD/G+dXzffCM7MC9f9lzoAfIX8tw52SWVmenwW6dMmVJlXR5Dj8gYTCYTJk6ciPfff7889H766SdMmDCh5l1fhAAefdTzoQcAhYXA4sXA44979nE9wLtGfKdPyyUHubnq1eDnB7RpI9uJW7QAIDs2jxw5gilTpgCQr/oKCgoQEhKiXp1EpAn33Xcf3njjDVgsFixbtgzx8fEVnZ9PPQUsW+b50KssOFiG3xNPqFeDi3lP8OXmAh07Ar/8Il8lqSkgAPjDH2D77DMkvvQSFi1aBEVRcPToUXTr1k3d2ohIUzIzM5GQkICdO3cCAIYNG4a1a9ciet8+ICFB3dArExwMbNwIjB+vdiUu4T3Bd++9wI4dcucVDVDMZrwSHo65P/wAgPfyiKh2QshdX2bPno0rV66gY0gIjtts8K/PmjxPadJEbvQRGal2JU7zjuD74ANg3DhtvDKqpADA8MhIPLFxI3dfIaI6ZWVlIeHBB/F/O3fiVgABahdUWUAAMHgw8P77ut/6TP/Bl5sLtGsHXLmidiW/YTeZILp1g99XX6m27ycR6YvYsAH2hAT4aWm0VyYkBFi3Dpg4Ue1KnKL/rk61b/w64CsE/DIygF271C6FiPSgtBSmRx7RZugBgNUK/N//ya3OdEzfwWezAa++qpn7ejW6dg144QW1qyAiPdi5U/uhUlwspzt1TN/Bt3u3DD+t++YbeVOYiMiRpUuB/Hy1q3AsP1/WqWP6Dr7nn3f+l6RZM+C+++S8dVqaPLWhuFjeOzxyRO5c0Ly5c49hs8kd1ImIanPypHxzVosWwJIlwLFj8vkxP1++v2SJ889lZdLS5IYdOqXf5pYrV4DrrnN+d5axY4F333X8PT/+KLuZTp9u/OM0awZcvdr4nyci77ZoEfDcc87NYsXEAHv2yHP3avLjj8CwYcCJE41/DEB2eP7978CCBc5dRyX6HfGlpbn2AMWcHCApSe6U8OKL8hekTOvWwGuvOXf9wsI6tzIjIgPbt8+50AsKArZvrwi9q1dlf8HSpRUvulu3BrZtk2fxOaOkRB54q1OuO0nV044ccU0355UrwF//CqxdK8OpzNKlwPHjFYs1b7sNCA2t38G1NQkMlGE9apTzNROR9/nmG+d+/s9/lrtXlbn3XuDDD+X7+/dXNKR06iS/9/XXnXu8o0ed+3kV6XfEt3+/PBHdWXv3Aq+8UjX0ACA7GzhwoOJjHx85vG8sqxVITW38zxOR9/rxx/qdnO5IbGzF+7m5FaEHyPfz8io+/tOfnHssQM6SaXD9dH3oN/icfXVUH507V7z/7bfO/Z9stwOff+58TUTkfY4dc376sUePivczMqp+TYiqn7vxRuceC5C3mo4dc/46KtBv8Ll70frTTwOVN5R++mnnr5mT4/w1iMj75OUBiuLcNcLCql6vpscoU8eZofUiRM2PowP6vcfnrrP2TCbZ3PLIIxWfW7wY2LLF+WtreaE9EamnqMi1p8rUtJemq/fXFEK3z2n6DT4fNwxWQ0NlwI0eLT9WFGDePCAx0TXX536dRFQTVzw3XL4MXH+9fL9Jk99+vfLnsrOdfzyTSbfPafqd6nSm0aQm0dHAZ59VhJ7VKk98cFXoAa5dfkFE3sNsdv7F/NdfV7z/+99XHeGZTPJzZVzRI2Ey6fY5Tb/B17Kl667Vty9w6BDwhz/Ij3/4ARgwQJ7v50q/+51rr0dE3qG2BecN8etBtgDk6G7kyIqPR44ELJaKj13x3KYoFSNMndHvzi3TpskTgZ11yy3Af/9b8cqlbHuxmhabb90KXLzYuMcxm+W9w4ceanSpROSlCgtlWDm7gP2bbyrW8uXkVGy8cf/9FduVnTkjuzqdvT/n7y9nxvz9nbuOCvR7j+/WW4HkZPkP74yOHasO1/38gMceq/l7jxxpfPD5+wO9ezfuZ4nIu5nNcvR0/nzjr1FUJNfnpaTI7RybNQPmz6/6PT/9JL/HFU0p7drpMvQAPU919u7tngYXdykoqJhKJSKqrm9f569x4oRchvXPf8r3rVb5duKE/Fy3bs7v01mmf3/XXEcF+p3qLC2Vr2g0egjtb3TuDKSnq10FEWnV+vVy+0RnZ7E8ITQUWL1abn2mQzoaMlXj7w9MmSKnJrUuNLTqukAiouri4pxfxO5Jrtj2TCX6DT4AePhhfcwxCyE3jCUiqo3FIp8ntL42zt9fNhfqdCkDoPfg69wZ6N5d7Soc8/OTB92GhKhdCRFp3dy5rl+j7Gq+vsCcOWpX4RR9Bx8APPmktkPF31+OTImI6hITA9x4I4RWG/d8feUSsPbt1a7EKRr9122A0aPlYnMNTnlaAZwYOhSiQwe1SyEinfhhyRI4eUCR+wQFOX+OnwboP/hMJmDTJs3NNysAfgTQc9cujB07FllZWWqXREQapigKVqxYgS53340nFAWa6+0MCZEnunvBDlT6Dz5AnpK+erWmpjxNZjOOPfUUgiwW7NixA127dsWWLVug19UjROQ+GRkZGDJkCGbPng2r1Yofx49HYLdu2lmr7Osr1wAmJKhdiWsIb6EoQkyaJERwsBCyj1K9t+BgIf71LyGEEOfPnxdDhw4VAAQAERsbK65evaruvxURacbatWtFSEiIACAiIiLEu+++K79w7pwQzZqp/3xmMgnRooUQ58+r+w/lQhp5OeECJhOweTNw++3qTnsGBwOzZpVvexYdHY2PPvoIa9asgcViwfnz5xGioZEpEamrsLAQVqsVEyZMwMmTJzF27Fj5hXbtgH37qm4urQaLBThwQJ5g4yX0u3NLbUpK5HFC//2v53d1CQ6Wbb7PPVfjoY8XLlxAYWEhOnXqBADIzs6G3W5HZGSkZ+skItUoioL09HTExMSUf7x3714MGTKk5h84ehQYPFiedu7Jp2sfH6BpU2D/fu0vG2sg7xnxlQkIkEdu3Hef50Z+ZedSLVki98Or5aTj6Ojo8tADgISEBN77IzKQsnt5/fr1w/lfN6T28fGpPfQAoFcv4MsvgTZtPPecFhwMtG0LpKZ6XegB3hh8gLwRu2oV8N57svElKMh9jxUcDHTtKk9uaMB6vcLCQuTm5uLKlSu499572flJ5MXKOja7d++Offv2wWw24/vvv6//BTp3Bk6fBh580P3hZzYDs2fLvYV1vl6vVirfY3S//Hwh4uOFMJuF8PNz3Q3fwEB5zWefFaK0tFGlKYoi1qxZIywWiwAgWrRoId5++22hKIqL/xGISC3fffedGDRoUHmDW1xcnPj5558bf8FDh4SIjhYiNNS1TSyhoUK0aydEWprr/uM1yvuDr8zJk0I88IDsuAwJafwvh8UiO62efFKIS5dcUlr1zs+xY8cKm83mkmsTkXqSk5OrdGwmJye75sIlJUIkJwvRp49zL+r9/eXP9+0rxPbtjX4RrzfeOdVZky5d5Fq/rCwgMRHo0QMIDJRr/2rrmvLxkaciBwfL77vtNmDDBuDnn4FnngFat3ZJadU7P9u0aQNfrW9US0R16tChA4qLixEXF4cTJ05g3Lhxrrmwv79s4jt8WN5mmTZNPh/5+8vnrMDAmn8uMFB+3d9fHnwbHw989ZW8hxgbq4/TblzA+7o6G8JuB86elb84hw/LULRaZeCFhABRUfJwyN695Y3eWppWXOnChQsIDw9HcHAwACAtLQ1RUVHs/CTSAUVRsGfPHowYMaL8c6dPn67S1OZW+fkyyI4cAb75Rj6fFRXJPofQUPmCv3dv+b9qL5NQkbGDT+Py8vLQvXt3WK1WLF++HBMmTIDJA+FLRA2XkZGB+Ph47N27F8nJya4b3ZHLGWeqU4cKCgrQqVMnXL58GZMmTcK4cePY+UmkMYqiYOXKlejevTv27t2LiIgIBNY21UiawODTsFatWlW597d9+3bExMQgKSmJ6/6INCAjIwN33nknZs2aBavVWn4v76677lK7NHKAU506ceHCBcyYMQMpKSkA5OL3lStXqlwVkXEdOHAAI0eOhNVqRUREBFauXMnpTZ3giE8nqnd+jhw5Uu2SiAytV69eaNWqles7NsntOOLTocuXLyMsLKz84y1btmDw4MHs/CRyI0VRsHHjRowfPx6WXzsiq/8tkj5wxKdDlf/QDh8+jMmTJ3PPTyI3KruXFx8fj/nz55d/nqGnTww+nYuMjMSQIUO45yeRG9TUselwQ2nSBU51egEhBNatW4dHH30U+fn5aNGiBZYvX46JEydy3R9RI1VelwcAcXFxWL58OSIiIlSujJzF4PMi1Ts///nPf2LBggUqV0WkPxcuXEDXrl3ZsemlGHxepmz098wzz+CLL77A9ddfr3ZJRLo0efJklJaWcpTnhRh8XqqkpAQBAQEAALvdjqeffhpz5sxh5ydRDRRFwapVq9CvXz/07t0bQNW/IfIubG7xUpX/YF955RU899xz7PwkqkHZqeizZ8/G1KlTUVpaCgAMPS/G4DOAsWPHYujQoez8JKqk+qnoERERWLx4Mfz9/dUujdyMU50Gwc5PogoZGRmYPn069u3bBwCYMGECli9fjvDwcHULI49g8BlM9c7PHTt2YMyYMeoWReRBJSUlaNeuHS5duoSIiAisWrUKY8eOVbss8iAGnwGVjf527NiB3bt387R3MpzXX38de/bs4SjPoBh8BiaEKJ/mvHjxIhYuXIgXX3yRnZ/kVco6Nn18fJCQkACg6u8+GQ+DjwDIXSmSk5N574+8SuV7eUFBQTh37hxat26tdlmkMnZ1EgDgxRdfZOcneY2aOjbffPNNhh4B4IiPKmHnJ3kDdmxSXRh89BuVOz99fX2Rnp6ODh06qF0WUb0MHToUH3/8MTs2qVYMPqqREALr16/HL7/8goULF6pdDlG9nTp1CkuWLMFLL73EUR7ViMFH9bZr1y5s3LgRq1atYucnaYKiKFi9ejU+/fRTbNmyhVPyVC8MPqoXRVHQpUsXnDlzhvf+SBOqn5f3ySef4I477lC5KtIDdnVSvfj4+CAlJYWdn6S6mk5FT05OZuhRvXHERw3Czk9SU/WOTZ6KTo3BER81iMlkwsyZM3H8+PHy0d/ChQtRWFiodmlkAOvXry9fl5ecnIytW7cy9KjBOOKjRisb/d1www0YPHgwAMBms8HX15ejP3IZm80GPz8/AEBRURGefPJJzJ8/n4FHjcbgI5d6+OGHceHCBXZ+ktPKOjZffvllHDp0CM2bN1e7JPISnOokl7l8+TI2btyIHTt28LR3ckpGRgbuvPNOzJo1C2fPnsWWLVvULom8CIOPXCYsLAzHjh1j5yc1Wm0dmw899JDapZEX4VQnuRw7P6kxqq/LY8cmuQtHfORyNXV+7tixg6FHDp09e7bKKI8dm+QuHPGRWwkhsGHDBowePRotW7YEAOTk5KBp06YMQkJOTg6aNWtW/vG6detwzz33MPDIrRh85FGlpaXo27cvfve737Hz08DKOjYXLFiA999/HwMGDFC7JDIQTnWSR/3vf//Dt99+y85PA6vcsZmfn49du3apXRIZDIOPPKpXr15V7v2x89M4auvYfOGFF9QujQyGU52kipo6P1977TWMGzdO7dLIDS5evIj77ruPHZukCRzxkSpq6vzMzs5Wuyxyk4CAABw7dowdm6QJHPGR6oQQ2L17N+66667yTs9vv/0WN9xwAzs/dez8+fNo3bo1/P39AQCfffYZOnbsyMAj1XHER6ozmUy4++67y0Pu3LlzuPHGG3nvT6cURcGKFSsQExODpUuXln/+1ltvZeiRJjD4SHNOnToFX19fdn7qUEZGBoYMGYLZs2fDarXizJkz/P+ONIfBR5ozatQodn7qTNkor3v37uXn5b377rvYvHkzp6tJc3iPjzSrps7Pt956CyNGjFC7NKokJycHsbGx5aeiT5gwAcuXL0d4eLi6hRHVgiM+0qzqnZ/Xrl1DVFSU2mVRNU2aNIHJZCof5SUlJTH0SNM44iNdEELg2LFjuPHGG8s//vTTT3H77bdzKk0FGRkZ8PX1RXR0NAC5Ti8wMJDNK6QLHPGRLphMpvLQA4CkpCQMGjQI48aN470/D6q8+8q0adOgKAoAICoqiqFHusHgI12y2+2wWCzYvn07Oz89pPIem1arFeHh4SgsLFS7LKIGY/CRLk2ePLnGzs/MzEy1S/M6lTs2q5+XFxISonZ5RA3Ge3ykazV1fu7Zswe9e/dWuzSvoCgK/vjHP+Kjjz4CIDs2X331VU5rkq5xxEe6Vrnzc9iwYQgPD0fXrl3VLstr+Pj4YMCAAVU6Nhl6pHcc8ZHXEEIgKysLrVq1AgDk5uYiJSUFY8eOZednA2RkZCAjIwODBw8GIA8Pzs3N5RIF8hoc8ZHXMJlM5aEHAI899hjGjx/Pzs96qtyxOWHCBPz8888AAH9/f4YeeRUGH3mtvn37lnd+xsTEICkpiZ2ftajesTl48GD4+vqqXRaRW3Cqk7zahQsXMGPGDKSkpAAA/vSnP2HlypWIjIxUuTJtUBQFq1evxrx582C1WhEREYGVK1fyQGDyagw+8nrVOz/DwsJw8uRJtGzZ0uO15OUBmZlAYSFgtwNBQUCTJsD11wNq3IacMWMG1q9fD4CnopNxMPjIMMpGf9dffz02bNjg9scTAkhNBQ4eBPbvB44cAbKzgcBAwMen4ntsNvlxTAxw++1Av37A8OFAaKjbS8TBgwcxbtw4LF++nKM8MgwGHxmKEALFxcUICgoCAKSmpuLcuXOYOHGiyzo/8/OBN94A/vUvGXSlpUBxcf1+1sdHBl5pKTB5MvDww4ArV2dkZGRg9+7dmDNnTvnnCgsLYTabXfcgRBrH4CPDKi4uRs+ePZGeno7Y2FisWrXKqXt/eXnA/PnApk0ywKxW5+rz8wP8/WXwrVgB9O3b+GspioJVq1Zh/vz5sFqtSElJwZ133ulcgUQ6xa5OMqyAgADMnTsXFovF6dPe9+wBbrgB2LhR3r9zNvQAOQVaWAikpQF33AHMnQsUFTX8OtVPRZ8wYQJ69OjhfIFEOsURHxle9c7Phoz+8vKA2bOBbduAggL31hkcDISHA8nJwM031/391Ud5ERERWLVqFcaOHeveQok0jsFHhN92frZv3x6nTp1yuJYtMxMYMAC4dKlxI7HGCg4GNmwA4uIcf9/zzz+PhQsXAuCp6ESVMfiIKikb/U2ZMgVTpkyp9fsuXZKjrl9+kY0onmY2AytXAlOn1v49V69exR133IGnnnqKozyiShh8RNWU/UmUdXmuXLkSzZs3L+/8zM4G+vQBLl6Ua/HUYjbL7tGyTMvIyMBzzz2HV199tbxrVQjBfUqJqmHwETmQkZGBLl26oLi4GLGxsVixYhXuuScSX3+tzkivOrMZ+OILBQcPVtzLW7x4MRYtWqR2aUSaxeAjcqD6vT+zeT4U5RkUF/urXRoAwGQSCAr6AYWFNwCw8V4eUT0w+Ijq4cKFC7j33ifx2WerAGjt1PFrCA5ehc2b2/FeHlE9+KldAJEetGkTjeLiTfDxEVAUtaupLhSK8hg6duS9PKL64AJ2onr45BPg1CkTFEWbfzLFxSb8unKBiOrAqU6iehgxAvjoI7WrcCwwEMjIAK67Tu1KiLRNmy9fiTTk4kV5uoLWmUzA6tVqV0GkfQw+ojqsWiWPD3LW4sXArl3A2bPAlStyOURuLnDsmFyM3q2bc9cvKgJefVXu8UlEteNUJ1Ed2rWTU4jOqusvraQEGD9ehmNjWSzAf/8L3HRT469B5O0YfEQOFBbKE9JdMYrKzJSH0n73nRzxhYYCw4ZVDamTJ+WBtI1lNgPLlgEPPuh8vUTeisFH5MChQzKc8vLcc32TCUhPBzp1kh8XFspNqJ0xaRLw9tvO10bkrbiOj8iBtDT3bE1mMgHNmwPDhwPR0RWf/9//nL/2oUPOX4PImzH4iBw4elSOwlylbVvg++9r/lp2NjBnjvOPcf68vJ/IvamJasauTiIHcnI88zgnT8pT1l0xWhNCGxtoE2kVR3xEDrhytAfIppbHHgP8/IBWrYDRo4H27YGuXYHUVGD6dCApybnH8PWVSxsCAlxTM5G3YXMLkQOxscDOne67vq8v8OGHwJ13yo+tVuCGG4CsLOeumZ8vOzyJ6Lc41UnkQIibD2Kw24Hdu6s+Xt++zl8zMNC5axB5MwYfkQNdugD+Ljh677bbZBdndSYTMHJk1c85OwcTHg748C+bqFa8x0fkQJ8+cl1dbq5z15k+Xa6v27cP+Oor2TQTHg788Y/y/l6Z3Fzn9wXt1cu5nyfydgw+Igd693Zdg0tgoFy3N3x4zV/PywMmTnRusby/PzBwYON/nsgIGHxEDoSHyy3LsrOdu8769TLQ+vUDoqKAsDD5+atXgdOngY8/BtasAX7+2bnHMZu5TydRXdjVSVSHuDhg2zZo8OT13woKknuCNm2qdiVE2sVb4ER1mDtXH0sDfHyAMWMYekR14YiPqA5CAB06AOfOqV2JYyEhsnmmTx+1KyHSNo74iOpgMgHz5rl/TZ+z2rRh6BHVB4OPqB7+/GdtbwEWEiJPeCeiujH4iOohJATYvNn5s/Lcwd9fdovGxaldCZE+8B4fUQPExQG7dgHFxWpXUsFikUsirrtO7UqI9IEjPqIGeO01bY36QkKAFSsYekQNweAjaoDmzYF//1sb4RccDIwdC0yerHYlRPrC4CNqoNtuA955R921fcHB8iij11/nSetEDcXgI2qEUaOA7dvVGfkFB8sDbLdtk2fvEVHDMPiIGmnECLnHZmSk3CrME8xm4K9/BbZskae4E1HDsauTyEnXrskwSkoCCgrc8xjBwUCrVkByMo8dInIWg4/IRfbulQvdr10D8vNdc82gILll2pw5wLPPansRPZFeMPiIXMhmA957D3jhBeDoUcBuB0pLG34di0We3/fXvwL33w+0bOn6WomMisFH5CZnz8p1fykpcoG5n5/swCwqkgEJyBMVAgLkW2GhvF94003AtGnydHY2rxC5HoOPyAMUBThzBkhLAy5dkiFns8lmlSZNgBtvBHr2BEJD1a6UyPsx+IiIyFC4nIGIiAyFwUdERIbC4CMiIkNh8BERkaEw+IiIyFAYfEREZCgMPiIiMhQGHxERGQqDj4iIDIXBR0REhsLgIyIiQ2HwERGRoTD4iIjIUBh8RERkKAw+IiIyFAYfEREZCoOPiIgMhcFHRESGwuAjIiJDYfAREZGhMPiIiMhQGHxERGQoDD4iIjIUBh8RERnK/wf1o5wR9HVv0AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 找到测量结果中出现几率最大的比特串\n",
    "cut_bitstring = max(prob_measure, key=prob_measure.get)\n",
    "print(\"找到的割的比特串形式：\", cut_bitstring)\n",
    "\n",
    "# 在图上画出上面得到的比特串对应的割\n",
    "node_cut = [\"blue\" if cut_bitstring[v] == \"1\" else \"red\" for v in V]\n",
    "\n",
    "edge_cut = [\n",
    "    \"solid\" if cut_bitstring[u] == cut_bitstring[v] else \"dashed\"\n",
    "    for (u, v) in E\n",
    "    ]\n",
    "nx.draw(\n",
    "        G,\n",
    "        pos,\n",
    "        node_color=node_cut,\n",
    "        style=edge_cut,\n",
    "        **options\n",
    ")\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，在这个例子中 QAOA 找到了图上的一个最大割。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[1] Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. [arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
